oj.uz

Submission #920838

# Submission time Handle Problem Language Result Execution time Memory
920838 2024-02-03T05:12:43 Z Warinchai Examination (JOI19_examination) C++14
0 / 100
 257 ms 23432 KB 
#include<bits/stdc++.h>
using namespace std;
int n,q;
struct point{
    int i,x,y,z;
    point(int id=0,int a=0,int b=0,int c=0){
        i=id,x=a,y=b,z=c;
    }
    bool operator<(const point &t){
        return x==t.x?y<t.y:x<t.x;
    }
};
vector<point>v;
int ans[600005];
point temp[600005];
struct fenwick{
    int info[600005];
    void upd(int id,int val){
        for(int i=id;i<=600000;i+=i&-i)info[i]+=val;
    }
    int fsum(int id){
        int ans=0;
        for(int i=id;i>0;i-=i&-i){
            ans+=info[i];
        }
        return ans;
    }
}fw;
void solve(int st,int en){
    if(st==en)return;
    int m=(st+en)/2;
    solve(st,m);
    solve(m+1,en);
    //cerr<<st<<" "<<en<<"\n";
    int i=st,j=m+1;
    int id=st;
    //cerr<<"in solve work\n";
    while(i<=m||j<=en){
        if(j>en||(i<=m&&v[i].y>=v[j].y)){
            temp[id++]=v[i];
            if(v[i].i<=n)fw.upd(v[i].z,1);
            i++;
        }else{
            temp[id++]=v[j];
            ans[v[j].i]+=fw.fsum(600000)-fw.fsum(v[j].z-1);
            j++;
        }
    }
    //cerr<<"in solve work\n";
    for(int i=st;i<=m;i++)if(v[i].i<=n)fw.upd(v[i].z,-1);
    for(int i=st;i<=en;i++)v[i]=temp[i];
}
vector<int>val;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        int a,b;
        cin>>a>>b;
        v.push_back(point(i,a,b,a+b));
        val.push_back(a);
        val.push_back(b);
        val.push_back(a+b);
    }
    for(int i=1;i<=q;i++){
        int a,b,c;
        cin>>a>>b>>c;
        v.push_back(point(n+i,a,b,c));
        val.push_back(a);
        val.push_back(b);
        val.push_back(c);
    }
    sort(val.begin(),val.end());
    //for(auto x:val)cerr<<x<<" ";
    //cerr<<"\n";
    for(auto &x:v){
        //cerr<<lower_bound(val.begin(),val.end(),x.x)-val.begin()<<"+"<<1<<"\n";
        x.x=lower_bound(val.begin(),val.end(),x.x)-val.begin()+1;
        x.y=lower_bound(val.begin(),val.end(),x.y)-val.begin()+1;
        x.z=lower_bound(val.begin(),val.end(),x.z)-val.begin()+1;
    }
    //cerr<<"work\n";
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    //for(auto x:v)cerr<<x.i<<" "<<x.x<<" "<<x.y<<" "<<x.z<<"\n";
    //cerr<<"work\n";
    solve(0,v.size()-1);
    //cerr<<"work\n";
    for(int i=n+1;i<=n+q;i++){
        cout<<ans[i]<<"\n";
    }
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10584 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 3 ms 10692 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Correct 3 ms 10944 KB Output is correct
6 Correct 3 ms 10588 KB Output is correct
7 Correct 9 ms 11100 KB Output is correct
8 Correct 9 ms 11148 KB Output is correct
9 Correct 9 ms 11100 KB Output is correct
10 Correct 8 ms 11188 KB Output is correct
11 Correct 8 ms 13144 KB Output is correct
12 Incorrect 7 ms 13148 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 22576 KB Output is correct
2 Correct 257 ms 22708 KB Output is correct
3 Correct 255 ms 23432 KB Output is correct
4 Incorrect 220 ms 20448 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 22576 KB Output is correct
2 Correct 257 ms 22708 KB Output is correct
3 Correct 255 ms 23432 KB Output is correct
4 Incorrect 220 ms 20448 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10584 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 3 ms 10692 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Correct 3 ms 10944 KB Output is correct
6 Correct 3 ms 10588 KB Output is correct
7 Correct 9 ms 11100 KB Output is correct
8 Correct 9 ms 11148 KB Output is correct
9 Correct 9 ms 11100 KB Output is correct
10 Correct 8 ms 11188 KB Output is correct
11 Correct 8 ms 13144 KB Output is correct
12 Incorrect 7 ms 13148 KB Output isn't correct
13 Halted 0 ms 0 KB -