oj.uz

답안 #210474

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
210474 2020-03-17T13:33:02 Z brcode Examination (JOI19_examination) C++14
0 / 100
 649 ms 27472 KB 
#include <iostream>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
using namespace std;
typedef tree<
pair<int, int>,
null_type,
less_equal<pair<int, int>>,
rb_tree_tag,
tree_order_statistics_node_update> ordered_set;



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 f(long long l,long long r){
    v1.clear();
    long long mid =(l+r)/2;
    
    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);
    ordered_set s1; 
    int cnt = 0;
    for(long long i=v1.size()-1;i>=0;i--){
        if(v1[i].type == 1){
            s1.insert(make_pair(v1[i].y,cnt++));
            //cout<<v1[i].y<<endl;
        }else{
            ans[v1[i].type]+=s1.size()-s1.order_of_key(make_pair(v1[i].y,0));
           // 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(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    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-1;
        
    }
    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-1;
    }
    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]<<"\n";
    }
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 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 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 16 ms 992 KB Output is correct
8 Correct 17 ms 1016 KB Output is correct
9 Correct 16 ms 1016 KB Output is correct
10 Incorrect 17 ms 888 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 649 ms 27472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 649 ms 27472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 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 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 16 ms 992 KB Output is correct
8 Correct 17 ms 1016 KB Output is correct
9 Correct 16 ms 1016 KB Output is correct
10 Incorrect 17 ms 888 KB Output isn't correct
11 Halted 0 ms 0 KB -