oj.uz

Submission #887003

# Submission time Handle Problem Language Result Execution time Memory
887003 2023-12-13T12:20:20 Z imarn Examination (JOI19_examination) C++14
20 / 100
 626 ms 72592 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,pii>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}].s=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=n;i>=1;i--)mp[{b[i].s,b[i].f}].f=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=upper_bound(c+1,c+n+1,b[j].s-1)-c;
            upd(1,1,n,id,mp[{b[j].f,b[j].s}].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=n;i>=1;i--)mp[{b[i].s,b[i].f}].f=i,swap(b[i].f,b[i].s);sort(b+1,b+n+1);
      |     ^~~
examination.cpp:69:70: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   69 |     for(int i=n;i>=1;i--)mp[{b[i].s,b[i].f}].f=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 5 ms 21344 KB Output is correct
2 Correct 5 ms 21432 KB Output is correct
3 Correct 5 ms 21340 KB Output is correct
4 Correct 5 ms 21436 KB Output is correct
5 Correct 4 ms 21336 KB Output is correct
6 Correct 4 ms 21340 KB Output is correct
7 Correct 13 ms 22764 KB Output is correct
8 Correct 13 ms 22620 KB Output is correct
9 Correct 13 ms 22560 KB Output is correct
10 Incorrect 11 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 601 ms 72464 KB Output is correct
2 Correct 558 ms 72268 KB Output is correct
3 Correct 575 ms 72380 KB Output is correct
4 Correct 311 ms 72008 KB Output is correct
5 Correct 491 ms 72008 KB Output is correct
6 Correct 177 ms 64580 KB Output is correct
7 Correct 564 ms 72592 KB Output is correct
8 Correct 562 ms 72536 KB Output is correct
9 Correct 511 ms 72516 KB Output is correct
10 Correct 346 ms 69316 KB Output is correct
11 Correct 200 ms 69328 KB Output is correct
12 Correct 137 ms 64112 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 601 ms 72464 KB Output is correct
2 Correct 558 ms 72268 KB Output is correct
3 Correct 575 ms 72380 KB Output is correct
4 Correct 311 ms 72008 KB Output is correct
5 Correct 491 ms 72008 KB Output is correct
6 Correct 177 ms 64580 KB Output is correct
7 Correct 564 ms 72592 KB Output is correct
8 Correct 562 ms 72536 KB Output is correct
9 Correct 511 ms 72516 KB Output is correct
10 Correct 346 ms 69316 KB Output is correct
11 Correct 200 ms 69328 KB Output is correct
12 Correct 137 ms 64112 KB Output is correct
13 Incorrect 626 ms 72480 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21344 KB Output is correct
2 Correct 5 ms 21432 KB Output is correct
3 Correct 5 ms 21340 KB Output is correct
4 Correct 5 ms 21436 KB Output is correct
5 Correct 4 ms 21336 KB Output is correct
6 Correct 4 ms 21340 KB Output is correct
7 Correct 13 ms 22764 KB Output is correct
8 Correct 13 ms 22620 KB Output is correct
9 Correct 13 ms 22560 KB Output is correct
10 Incorrect 11 ms 22620 KB Output isn't correct
11 Halted 0 ms 0 KB -