oj.uz

Submission #886999

# Submission time Handle Problem Language Result Execution time Memory
886999 2023-12-13T12:11:24 Z imarn Examination (JOI19_examination) C++14
20 / 100
 579 ms 71012 KB 
#include "bits/stdc++.h"
#define f first
#define s second
#define ll long long
#define pb push_back
#define pii pair<ll,ll>
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
using namespace std;
const int N=1e5+5;
struct query{
    ll i,x,y,z;
    bool operator<(const query &o)const{return x>o.x;}
};
struct fenwick{
    vector<ll>v,fw;
    void build(){
        fw.resize(v.size()+1,0);
    }
    void upd(ll i){
        i = upper_bound(all(v),i)-v.begin();
        //cout<<i<<"\n";
        for(;i<sz(fw);i+=i&-i)fw[i]++;
    }
    int qr(ll i,int res=0){
        i = upper_bound(all(v),i)-v.begin();
        for(;i;i-=i&-i)res+=fw[i];
        return res;
    }
}t[4*N];
pii b[N];
ll c[N];
void build(int i,int l,int r){
    if(l==r){
        t[i].v.pb(b[l].s+b[l].f);t[i].build();
        return;
    }int m=(l+r)>>1;
    build(2*i,l,m);build(2*i+1,m+1,r);
    int li=0,ri=0;
    while(li<t[2*i].v.size()&&ri<t[2*i+1].v.size()){
        if(t[2*i].v[li]<t[2*i+1].v[ri])t[i].v.pb(t[2*i].v[li++]);
        else t[i].v.pb(t[2*i+1].v[ri++]);
    }while(li<t[2*i].v.size())t[i].v.pb(t[2*i].v[li++]);
    while(ri<t[2*i+1].v.size())t[i].v.pb(t[2*i+1].v[ri++]);
    t[i].build();
}
void upd(int i,int l,int r,int idx,ll v){
    if(r<idx||l>idx)return;
    if(l==r){
        t[i].upd(v);return;
    }
    int m=(l+r)>>1;
    upd(2*i,l,m,idx,v);upd(2*i+1,m+1,r,idx,v);
    t[i].upd(v);
}
int qr(int i,int l,int r,int tl,int tr,ll v){
    if(r<tl||l>tr)return 0;
    if(r<=tr&&l>=tl){
        return t[i].qr(v);
    }int m=(l+r)>>1;
    return qr(2*i,l,m,tl,tr,v)+qr(2*i+1,m+1,r,tl,tr,v);
}
map<pii,ll>mp;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>b[i].s>>b[i].f,c[i]=b[i].f,mp[{b[i].s,b[i].f}]=b[i].f+b[i].s;
    sort(b+1,b+1+n);sort(c+1,c+n+1);build(1,1,n);
    for(int i=1;i<=n;i++)swap(b[i].f,b[i].s);sort(b+1,b+n+1);
    query qq[q];
    for(int i=0;i<q;i++)cin>>qq[i].x>>qq[i].y>>qq[i].z,qq[i].i=i;
    sort(qq,qq+q);
    int ans[q];int j=n;
    for(int i=0;i<q;i++){
        while(j>0&&b[j].f>=qq[i].x){
            int id=lower_bound(c+1,c+n+1,b[j].s)-c;
            upd(1,1,n,id,mp[{b[j].f,b[j].s}]);
            j--;
        }int id=lower_bound(c+1,c+1+n,qq[i].y)-c;
        ans[qq[i].i] = qr(1,1,n,id,n,1e16)-qr(1,1,n,id,n,qq[i].z-1);
    }for(int i=0;i<q;i++)cout<<ans[i]<<"\n";
}

Compilation message

examination.cpp: In function 'void build(int, int, int)':
examination.cpp:40:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     while(li<t[2*i].v.size()&&ri<t[2*i+1].v.size()){
      |           ~~^~~~~~~~~~~~~~~~
examination.cpp:40:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     while(li<t[2*i].v.size()&&ri<t[2*i+1].v.size()){
      |                               ~~^~~~~~~~~~~~~~~~~~
examination.cpp:43:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     }while(li<t[2*i].v.size())t[i].v.pb(t[2*i].v[li++]);
      |            ~~^~~~~~~~~~~~~~~~
examination.cpp:44:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     while(ri<t[2*i+1].v.size())t[i].v.pb(t[2*i+1].v[ri++]);
      |           ~~^~~~~~~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:69:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   69 |     for(int i=1;i<=n;i++)swap(b[i].f,b[i].s);sort(b+1,b+n+1);
      |     ^~~
examination.cpp:69:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   69 |     for(int i=1;i<=n;i++)swap(b[i].f,b[i].s);sort(b+1,b+n+1);
      |                                              ^~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21336 KB Output is correct
2 Correct 4 ms 21340 KB Output is correct
3 Correct 4 ms 21196 KB Output is correct
4 Correct 4 ms 21192 KB Output is correct
5 Correct 4 ms 21340 KB Output is correct
6 Correct 4 ms 21340 KB Output is correct
7 Correct 13 ms 22620 KB Output is correct
8 Correct 13 ms 22692 KB Output is correct
9 Correct 12 ms 22704 KB Output is correct
10 Incorrect 10 ms 22620 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 70944 KB Output is correct
2 Correct 544 ms 70892 KB Output is correct
3 Correct 538 ms 70956 KB Output is correct
4 Correct 282 ms 70736 KB Output is correct
5 Correct 474 ms 70624 KB Output is correct
6 Correct 177 ms 64760 KB Output is correct
7 Correct 517 ms 70724 KB Output is correct
8 Correct 504 ms 71012 KB Output is correct
9 Correct 497 ms 70980 KB Output is correct
10 Correct 342 ms 68548 KB Output is correct
11 Correct 188 ms 68420 KB Output is correct
12 Correct 134 ms 64328 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 70944 KB Output is correct
2 Correct 544 ms 70892 KB Output is correct
3 Correct 538 ms 70956 KB Output is correct
4 Correct 282 ms 70736 KB Output is correct
5 Correct 474 ms 70624 KB Output is correct
6 Correct 177 ms 64760 KB Output is correct
7 Correct 517 ms 70724 KB Output is correct
8 Correct 504 ms 71012 KB Output is correct
9 Correct 497 ms 70980 KB Output is correct
10 Correct 342 ms 68548 KB Output is correct
11 Correct 188 ms 68420 KB Output is correct
12 Correct 134 ms 64328 KB Output is correct
13 Incorrect 579 ms 70780 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21336 KB Output is correct
2 Correct 4 ms 21340 KB Output is correct
3 Correct 4 ms 21196 KB Output is correct
4 Correct 4 ms 21192 KB Output is correct
5 Correct 4 ms 21340 KB Output is correct
6 Correct 4 ms 21340 KB Output is correct
7 Correct 13 ms 22620 KB Output is correct
8 Correct 13 ms 22692 KB Output is correct
9 Correct 12 ms 22704 KB Output is correct
10 Incorrect 10 ms 22620 KB Output isn't correct
11 Halted 0 ms 0 KB -