oj.uz

Submission #522164

# Submission time Handle Problem Language Result Execution time Memory
522164 2022-02-04T02:52:12 Z phamhoanghiep Examination (JOI19_examination) C++14
100 / 100
 874 ms 50940 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
struct qry{
    int x,y,z;
    int id;
    qry (int _x, int _y, int _z, int _id): x(_x), y(_y), z(_z), id(_id) {};
};
bool cmp(qry q1, qry q2) {
    if(q1.x==q2.x) {
        if(q1.y==q2.y) {
            if(q1.z==q2.z) return q1.id<q2.id;
            return q1.z>q2.z;
        }
        return q1.y>q2.y;
    }
    return q1.x>q2.x;
}
vector<qry> vt;
int ans[maxn];
int S[maxn];
int T[maxn];
int X[maxn];
int Y[maxn];
int Z[maxn];
vector<int> val;
map<int,int> yay;
int n,q;
struct Binary_indexed_tree{
    int bit[2000000];
    int n;
    void init(int _n) {
        n=_n;
        for(int i=0 ; i<=n ; i++) bit[i]=0;
    }
    void upd(int pos, int val) {
        for(int i=pos ; i<=n ; i+=i&(-i)) bit[i]+=val;
    }
    int get_val(int pos) {
        int ans=0;
        for(int i=pos ; i>0 ; i-=i&(-i)) ans+=bit[i];
        return ans;
    }
}BIT;
void cdq(int l, int r) {
    if(l==r) return;
    int mid=(l+r)/2;
    cdq(l,mid); cdq(mid+1,r);
    int sum=0;
    int l_it=l;
    int r_it=mid+1;
    vector<int> record; // record the queries to reverse on BIT
    vector<qry> tmp; // for sorting according to y
    while(l_it<=mid&&r_it<=r) {
        if(vt[l_it].y>=vt[r_it].y) {
            if(!vt[l_it].id) {
                BIT.upd(vt[l_it].z,1);
                sum++;
                record.push_back(vt[l_it].z);
            }
            tmp.push_back(vt[l_it++]);
        }
        else {
            if(vt[r_it].id) {
                ans[vt[r_it].id]+=sum-BIT.get_val(vt[r_it].z-1);
            }
            tmp.push_back(vt[r_it++]);
        }
    }
    while(l_it<=mid) tmp.push_back(vt[l_it++]);
    while(r_it<=r) {
        if(vt[r_it].id) ans[vt[r_it].id]+=sum-BIT.get_val(vt[r_it].z-1);
        tmp.push_back(vt[r_it++]);
    }
    for(int i=l ; i<=r ; i++) vt[i]=tmp[i-l];
    for(int i: record) BIT.upd(i,-1);
    record.clear();
    tmp.clear();
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("draft.inp","r",stdin);
    //freopen("draft.out","w",stdout);
    cin>>n>>q;
    for(int i=1 ; i<=n ; i++) {
        cin>>S[i]>>T[i];
        val.push_back(S[i]);
        val.push_back(T[i]);
        val.push_back(S[i]+T[i]);
    }
    for(int i=1 ; i<=q ; i++) {
        cin>>X[i]>>Y[i]>>Z[i];
        val.push_back(X[i]);
        val.push_back(Y[i]);
        val.push_back(Z[i]);
    }
    sort(val.begin(),val.end());
    int cr=0;
    for(int i=0 ; i<val.size() ; i++) {
        if(!i||val[i]!=val[i-1]) {
            cr++;
            yay[val[i]]=cr;
        }
    }
    BIT.init(cr+5);
    for(int i=1 ; i<=n ; i++) {
        vt.push_back(qry(yay[S[i]],yay[T[i]],yay[S[i]+T[i]],0));
    }
    for(int i=1 ; i<=q ; i++) {
        vt.push_back(qry(yay[X[i]],yay[Y[i]],yay[Z[i]],i));
    }
    sort(vt.begin(),vt.end(),&cmp);
    cdq(0,n+q-1);
    for(int i=1 ; i<=q ; i++) {
        cout<<ans[i]<<'\n';
    }
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:100:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for(int i=0 ; i<val.size() ; i++) {
      |                   ~^~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 12 ms 1740 KB Output is correct
8 Correct 12 ms 1716 KB Output is correct
9 Correct 16 ms 1820 KB Output is correct
10 Correct 10 ms 1484 KB Output is correct
11 Correct 11 ms 1448 KB Output is correct
12 Correct 5 ms 844 KB Output is correct
13 Correct 10 ms 1708 KB Output is correct
14 Correct 10 ms 1740 KB Output is correct
15 Correct 11 ms 1744 KB Output is correct
16 Correct 9 ms 1200 KB Output is correct
17 Correct 8 ms 1356 KB Output is correct
18 Correct 4 ms 856 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 22428 KB Output is correct
2 Correct 410 ms 22288 KB Output is correct
3 Correct 407 ms 22276 KB Output is correct
4 Correct 288 ms 20272 KB Output is correct
5 Correct 362 ms 20256 KB Output is correct
6 Correct 165 ms 15404 KB Output is correct
7 Correct 369 ms 24648 KB Output is correct
8 Correct 374 ms 24556 KB Output is correct
9 Correct 399 ms 24232 KB Output is correct
10 Correct 295 ms 21476 KB Output is correct
11 Correct 273 ms 21468 KB Output is correct
12 Correct 132 ms 15220 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 22428 KB Output is correct
2 Correct 410 ms 22288 KB Output is correct
3 Correct 407 ms 22276 KB Output is correct
4 Correct 288 ms 20272 KB Output is correct
5 Correct 362 ms 20256 KB Output is correct
6 Correct 165 ms 15404 KB Output is correct
7 Correct 369 ms 24648 KB Output is correct
8 Correct 374 ms 24556 KB Output is correct
9 Correct 399 ms 24232 KB Output is correct
10 Correct 295 ms 21476 KB Output is correct
11 Correct 273 ms 21468 KB Output is correct
12 Correct 132 ms 15220 KB Output is correct
13 Correct 475 ms 26424 KB Output is correct
14 Correct 453 ms 25128 KB Output is correct
15 Correct 408 ms 24728 KB Output is correct
16 Correct 343 ms 22428 KB Output is correct
17 Correct 353 ms 22464 KB Output is correct
18 Correct 157 ms 16376 KB Output is correct
19 Correct 500 ms 26552 KB Output is correct
20 Correct 459 ms 25808 KB Output is correct
21 Correct 432 ms 26416 KB Output is correct
22 Correct 285 ms 21480 KB Output is correct
23 Correct 269 ms 21660 KB Output is correct
24 Correct 136 ms 15212 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 12 ms 1740 KB Output is correct
8 Correct 12 ms 1716 KB Output is correct
9 Correct 16 ms 1820 KB Output is correct
10 Correct 10 ms 1484 KB Output is correct
11 Correct 11 ms 1448 KB Output is correct
12 Correct 5 ms 844 KB Output is correct
13 Correct 10 ms 1708 KB Output is correct
14 Correct 10 ms 1740 KB Output is correct
15 Correct 11 ms 1744 KB Output is correct
16 Correct 9 ms 1200 KB Output is correct
17 Correct 8 ms 1356 KB Output is correct
18 Correct 4 ms 856 KB Output is correct
19 Correct 384 ms 22428 KB Output is correct
20 Correct 410 ms 22288 KB Output is correct
21 Correct 407 ms 22276 KB Output is correct
22 Correct 288 ms 20272 KB Output is correct
23 Correct 362 ms 20256 KB Output is correct
24 Correct 165 ms 15404 KB Output is correct
25 Correct 369 ms 24648 KB Output is correct
26 Correct 374 ms 24556 KB Output is correct
27 Correct 399 ms 24232 KB Output is correct
28 Correct 295 ms 21476 KB Output is correct
29 Correct 273 ms 21468 KB Output is correct
30 Correct 132 ms 15220 KB Output is correct
31 Correct 475 ms 26424 KB Output is correct
32 Correct 453 ms 25128 KB Output is correct
33 Correct 408 ms 24728 KB Output is correct
34 Correct 343 ms 22428 KB Output is correct
35 Correct 353 ms 22464 KB Output is correct
36 Correct 157 ms 16376 KB Output is correct
37 Correct 500 ms 26552 KB Output is correct
38 Correct 459 ms 25808 KB Output is correct
39 Correct 432 ms 26416 KB Output is correct
40 Correct 285 ms 21480 KB Output is correct
41 Correct 269 ms 21660 KB Output is correct
42 Correct 136 ms 15212 KB Output is correct
43 Correct 864 ms 50832 KB Output is correct
44 Correct 855 ms 50852 KB Output is correct
45 Correct 874 ms 50940 KB Output is correct
46 Correct 549 ms 38540 KB Output is correct
47 Correct 547 ms 38492 KB Output is correct
48 Correct 164 ms 16404 KB Output is correct
49 Correct 777 ms 50660 KB Output is correct
50 Correct 838 ms 50644 KB Output is correct
51 Correct 747 ms 50472 KB Output is correct
52 Correct 437 ms 33880 KB Output is correct
53 Correct 343 ms 28120 KB Output is correct