QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#129428#6136. AirdropEnergy_is_not_over#WA 255ms8064kbC++174.2kb2023-07-22 19:26:002023-07-22 19:26:01

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-22 19:26:01]
  • 评测
  • 测评结果:WA
  • 用时:255ms
  • 内存:8064kb
  • [2023-07-22 19:26:00]
  • 提交

answer

//
// Created by Barichek on 22.07.2023 14:00:51
//

#include <bits/stdc++.h>

#define F first
#define S second
#define MP make_pair
#define PB push_back

#define all(a) a.begin(), a.end()
#define len(a) (int) (a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

#ifdef Energy_is_not_over
#define DEBUG for (bool ____DEBUG = true; ____DEBUG; ____DEBUG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl

template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }

#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = 1e5+10, inf = 1000111222;

int have[2*max_n];

int T;

void solve()
{
    int n,y0;
    cin>>n>>y0;
    y0++;
    vector<pii> xy(n);
    for (int i=0;i<n;i++){
        cin>>xy[i].fir>>xy[i].sec;
        xy[i].fir++;
        xy[i].sec++;
    }
    vector<int> Xs;
    for (auto i:xy){
        Xs.pb(i.fir-1);
        Xs.pb(i.fir);
        Xs.pb(i.fir+1);
    }
    sort(all(Xs));
    Xs.resize(unique(all(Xs))-Xs.begin());
    vector<int> ans(len(Xs),0);
    DEBUG{
        for (auto i:Xs){
            cerr<<i<<" ";
        }
        cerr<<"\n";
    };
    for (int i=0;i<len(Xs);i++){
//        LOG(i,ans[i]);
//        LOG(i,Xs[i],lower_bound(all(xy),mp(Xs[i],+inf))-lower_bound(all(xy),mp(Xs[i]-1,+inf)));
        ans[i]+=lower_bound(all(xy),mp(Xs[i],+inf))-lower_bound(all(xy),mp(Xs[i]-1,+inf));
    }
    DEBUG{
        cerr<<"after base ans :: ";
        for (int i=0;i<len(Xs);i++){
            cerr<<Xs[i]<<" "<<ans[i]<<", ";
        }
        cerr<<"\n";
    };
    {
        T++;
        int cnt_have_equal_T=0;
        int p=0;
        for (int X_id=0;X_id<len(Xs);X_id++){
            const int X=Xs[X_id];
            int r_p=p;
            while (r_p<len(xy) && xy[r_p].fir<X){
                r_p++;
            }
            for (int i=p;i<r_p;i++){
                int val=max_n-xy[i].fir+abs(y0-xy[i].sec);
                if (have[val]<T){
                    have[val]=T;
                    cnt_have_equal_T++;
                }
                else{
                    cnt_have_equal_T-=(have[val]==T);
                    have[val]=T+1;
                }
            }
            for (int i=p;i<r_p;i++){
                int val=max_n-xy[i].fir+abs(y0-xy[i].sec);
                if (have[val]==T+1){
                    have[val]=-1;
                }
            }
            ans[X_id]+=cnt_have_equal_T;
            p=r_p;
        }
    }
    DEBUG{
        cerr<<"after left ans :: ";
        for (int i=0;i<len(Xs);i++){
            cerr<<Xs[i]<<" "<<ans[i]<<", ";
        }
        cerr<<"\n";
    };
    {
        T++;
        int cnt_have_equal_T=0;
        int p=len(xy)-1;
        for (int X_id=len(Xs)-1;X_id>=0;X_id--){
            const int X=Xs[X_id];
            int r_p=p;
            while (r_p>=0 && xy[r_p].fir>X){
                r_p--;
            }
            for (int i=p;i>r_p;i--){
                int val=xy[i].fir+abs(y0-xy[i].sec);
                if (have[val]<T){
                    have[val]=T;
                    cnt_have_equal_T++;
                }
                else{
                    cnt_have_equal_T-=(have[val]==T);
                    have[val]=T+1;
                }
            }
            for (int i=p;i>r_p;i--){
                int val=xy[i].fir+abs(y0-xy[i].sec);
                if (have[val]==T+1){
                    have[val]=-1;
                }
            }
            ans[X_id]+=cnt_have_equal_T;
            p=r_p;
        }
    }
    DEBUG{
        cerr<<"after right ans :: ";
        for (int i=0;i<len(Xs);i++){
            cerr<<Xs[i]<<" "<<ans[i]<<", ";
        }
        cerr<<"\n";
    };
    cout<<*min_element(all(ans))<<" "<<*max_element(all(ans))<<"\n";
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int tests;
    cin>>tests;
    while (tests--){
        solve();
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3528kb

input:

3
3 2
1 2
2 1
3 5
3 3
2 1
2 5
4 3
2 3
1 3
4 3

output:

1 3
0 3
2 2

result:

ok 6 numbers

Test #2:

score: -100
Wrong Answer
time: 255ms
memory: 8064kb

input:

3508
6 1
7 1
1 1
9 1
10 1
3 1
4 1
3 8
8 9
8 7
1 8
9 5
10 1
10 8
10 2
5 1
9 9
5 9
10 9
6 4
4 7
6 7
10 5
3 8
9 5
9 9
7 5
4 7
10 5
6 9
9 5
6 6
9 3
3 2
5 1
3 8
6 4
5 9
10 2
2 9
10 10
10 8
4 1
7 1
6 1
3 1
5 1
2 4
9 3
3 3
4 5
3 8
9 6
9 9
6 3
9 5
9 3
2 9
9 1
9 2
4 1
5 4
5 6
6 5
9 8
4 1
2 1
5 1
7 1
3 1
9 10...

output:

0 6
0 3
0 9
0 4
1 10
0 2
0 4
0 2
1 4
1 4
1 4
2 9
0 6
0 7
1 8
0 2
0 6
4 10
1 9
1 3
2 4
0 2
2 4
1 7
2 6
1 9
2 2
0 2
1 5
0 6
2 2
1 1
1 5
0 6
3 8
1 1
0 7
2 5
0 7
0 2
0 7
1 1
0 6
1 4
0 6
0 6
0 6
0 2
0 9
0 6
1 1
2 8
2 2
2 2
0 9
2 9
0 6
0 4
1 5
0 2
1 4
0 3
0 5
0 4
1 4
2 2
2 6
2 6
0 6
0 2
0 6
0 4
1 8
0 5
1 ...

result:

wrong answer 1st numbers differ - expected: '6', found: '0'