oj.uz

Submission #210470

# Submission time Handle Problem Language Result Execution time Memory
210470 2020-03-17T13:02:15 Z brcode Examination (JOI19_examination) C++14
0 / 100
 3000 ms 21468 KB 
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

const long long MAXN = 5e5+5;
long long ans[MAXN];
long long seg[4*MAXN];
struct student{
    long long type,x,y,z;
};
student hold[MAXN];
long long n,q;
bool sortfirst(student a,student b){
    if(a.x==b.x){
        return a.type>b.type;
    }
    return a.x<b.x;
}
bool sortsecond(student a,student b){
    if(a.y==b.y){
        return a.type>b.type;
    }
    return a.y<b.y;
}
bool sortthird(student a,student b){
    if(a.z==b.z){
        return a.type>b.type;
    }
    return a.z<b.z;
}
vector<student> v1;
void build(long long curr,long long l,long long r){
    if(l==r){
        seg[curr] = 0;
        return;
    }
    long long mid = (l+r)/2;
    build(2*curr,l,mid);
    build(2*curr+1,mid+1,r);
    seg[curr] = seg[2*curr]+seg[2*curr+1];
}
void update(long long curr,long long l,long long r,long long ind){
    if(l==r){
        seg[curr]++;
        return;
    }
    long long mid = (l+r)/2;
    if(ind <= mid){
        update(2*curr,l,mid,ind);
    }else{
        update(2*curr+1,mid+1,r,ind);
    }
    seg[curr] = seg[2*curr]+seg[2*curr+1];
}
long long query(long long curr,long long l,long long r,long long tl,long long tr){
    if(tr<l||tl>r){
        return 0;
    }
    if(tl<=l && r<=tr){
        //cout<<tl<<" "<<tr<<endl;
        return seg[curr];
    }
    long long mid = (l+r)/2;
    return query(2*curr,l,mid,tl,tr)+query(2*curr+1,mid+1,r,tl,tr);
}
void f(long long l,long long r){
    v1.clear();
    long long mid =(l+r)/2;
    build(1,1,n+q+1);
    for(long long i=l;i<=mid;i++){
        if(hold[i].type != 1){
            
            v1.push_back(hold[i]);
        }
    }
    for(long long i=mid+1;i<=r;i++){
        if(hold[i].type == 1){
            v1.push_back(hold[i]);
        }
    }
    sort(v1.begin(),v1.end(),sortfirst);
    for(long long i=v1.size()-1;i>=0;i--){
        if(v1[i].type == 1){
            update(1,1,n+q+1,v1[i].y);
            //cout<<v1[i].y<<endl;
        }else{
            ans[v1[i].type]+=query(1,1,n+q+1,v1[i].y,n+q+1);
            //cout<<l<<" "<<r<<" "<<" "<<v1[i].type<<" "<<ans[v1[i].type]<<endl;
        }
    }
    if(l!=mid){
        f(l,mid);
    }
    if(r!=mid+1){
        f(mid+1,r);
    }
    
}
int main(){
    cin>>n>>q;
    //cout<<n<<" "<<q<<endl;
    for(long long i=1;i<=n;i++){
        long long s,t;
        cin>>s>>t;
        hold[i].type = 1;
        hold[i].x=s;
        hold[i].y=t;
        hold[i].z=s+t;
    }
    for(long long i=n+1;i<=n+q;i++){
        long long u,v,w;
        cin>>u>>v>>w;
        hold[i].type=i;
        hold[i].x=u;
        hold[i].y=v;
        hold[i].z=w;
        //queries.push_back(make_pair(make_pair(x,y),z));
    }
    sort(hold+1,hold+n+q+1,sortfirst);
    long long curr = 0;
    for(long long i=1;i<=n+q;i++){
        if(hold[i].x!=hold[i-1].x){
            curr++;
        }
        
        hold[i].x=curr;
        
    }
    curr=0;
    sort(hold+1,hold+n+q+1,sortsecond);
    for(long long i=1;i<=n+q;i++){
        if(hold[i].y!=hold[i-1].y){
            curr++;
        }
        hold[i].y=curr;
    }
    sort(hold+1,hold+n+q+1,sortthird);
    curr = 0;
    for(long long i=1;i<=n+q;i++){
        if(hold[i].z!=hold[i+1].z){
            curr++;
            
        }
        //cout<<hold[i].z<<endl;
        hold[i].z=curr-1;
    }
    
    f(1,n+q);
    for(long long i=n+1;i<=n+q;i++){
        cout<<ans[i]<<endl;
    }
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 328 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 222 ms 1148 KB Output is correct
8 Correct 215 ms 1144 KB Output is correct
9 Correct 234 ms 1272 KB Output is correct
10 Incorrect 207 ms 1020 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3018 ms 21468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3018 ms 21468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 328 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 222 ms 1148 KB Output is correct
8 Correct 215 ms 1144 KB Output is correct
9 Correct 234 ms 1272 KB Output is correct
10 Incorrect 207 ms 1020 KB Output isn't correct
11 Halted 0 ms 0 KB -