oj.uz

Submission #1050895

# Submission time Handle Problem Language Result Execution time Memory
1050895 2024-08-09T16:30:41 Z MrAndria Examination (JOI19_examination) C++14
100 / 100
 1108 ms 143764 KB 
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
#define ordered_set tree<pair <int,int> , null_type,less<pair <int,int> >, rb_tree_tag,tree_order_statistics_node_update> 
//#define int long long
int n,q,ans[200005];
vector <int> v;
map <int,int> mp;
pair < pair <int,int> , pair <int,int> > pr[200005];
ordered_set bit[200100];
int sum(int idx,int val) {
    // cout<<"START2"<<" "<<idx<<endl;
    int ret = 0;
    for (idx; idx > 0; idx -= idx & -idx){
        ret += bit[idx].order_of_key(make_pair(-val,n+q+2));
        // cout<<ret<<" "<<idx <<" "<<bit[idx].size()<<endl;
    }
        

    return ret;
}

int sum(int l, int r,int val) {
    // cout<<"START1"<<" "<<val<<endl;

    return sum(r,val) - sum(l - 1,val);
}

void add(int idx, int delta,int y) {
    // cout<<idx<<" "<<delta<<" "<<y<<" "<<n+q+1<<" THIS SHIT"<<endl;
    for (idx; idx <= n+q+1; idx += idx & -idx){
        bit[idx].insert(make_pair(-delta,y));
        // cout<<idx<<" "<<delta<<endl;
    }
    
}
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>pr[i].ff.ff>>pr[i].ff.ss;
        pr[i].ss.ff=pr[i].ff.ff+pr[i].ff.ss;
        pr[i].ss.ss=1;
    }
    for(int i=1;i<=q;i++){
        cin>>pr[i+n].ff.ff>>pr[i+n].ff.ss>>pr[i+n].ss.ff;
        pr[i+n].ss.ss=-i;
    }
    sort(pr+1,pr+n+q+1);
    for(int i=1;i<=n+q;i++){
        mp[pr[i].ff.ff]++;
        if(mp[pr[i].ff.ff]==1){
            v.pb(pr[i].ff.ff);
        }
    }
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();i++){
        mp[v[i]]=i+1;
    }
    for(int i=1;i<=n+q;i++){
        pr[i].ff.ff=mp[pr[i].ff.ff];
    }
    v.clear();
    mp.clear();

    for(int i=1;i<=n+q;i++){
        mp[pr[i].ff.ss]++;
        if(mp[pr[i].ff.ss]==1){
            v.pb(pr[i].ff.ss);
        }
    }
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();i++){
        mp[v[i]]=i+1;
    }
    for(int i=1;i<=n+q;i++){
        pr[i].ff.ss=mp[pr[i].ff.ss];
    }
    v.clear();
    mp.clear();
    for(int i=1;i<=n+q;i++){
        mp[pr[i].ss.ff]++;
        if(mp[pr[i].ss.ff]==1){
            v.pb(pr[i].ss.ff);
        }
    }
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();i++){
        mp[v[i]]=i+1;
    }
    for(int i=1;i<=n+q;i++){
        pr[i].ss.ff=mp[pr[i].ss.ff];
    }
    // for(int i=1;i<=n+q;i++){
    //     cout<<pr[i].ff.ff<<" "<<pr[i].ff.ss<<" "<<pr[i].ss.ff<<" "<<pr[i].ss.ss<<endl;
    // }
    for(int i=n+q;i>=1;i--){
        if(pr[i].ss.ss==1){
            add(pr[i].ff.ss,pr[i].ss.ff,i);

        }else{
            ans[-pr[i].ss.ss]=sum(pr[i].ff.ss,n+q,pr[i].ss.ff);
        }
    }
    // for(int i=1;i<=n+q+1;i++){
    //     // cout<<i<<" "<<bit[i].size()<<endl;
    //     // cout<<endl;
    // }
    for(int i=1;i<=q;i++){
        cout<<ans[i]<<" ";
        
    }
    cout<<endl;
}

Compilation message

examination.cpp: In function 'int sum(int, int)':
examination.cpp:20:10: warning: statement has no effect [-Wunused-value]
   20 |     for (idx; idx > 0; idx -= idx & -idx){
      |          ^~~
examination.cpp: In function 'void add(int, int, int)':
examination.cpp:37:10: warning: statement has no effect [-Wunused-value]
   37 |     for (idx; idx <= n+q+1; idx += idx & -idx){
      |          ^~~
examination.cpp: In function 'int main()':
examination.cpp:62:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~
examination.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~
examination.cpp:93:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19288 KB Output is correct
2 Correct 8 ms 19292 KB Output is correct
3 Correct 8 ms 19208 KB Output is correct
4 Correct 9 ms 19292 KB Output is correct
5 Correct 8 ms 19288 KB Output is correct
6 Correct 8 ms 19288 KB Output is correct
7 Correct 22 ms 23028 KB Output is correct
8 Correct 20 ms 22876 KB Output is correct
9 Correct 20 ms 22872 KB Output is correct
10 Correct 20 ms 23896 KB Output is correct
11 Correct 18 ms 22980 KB Output is correct
12 Correct 21 ms 23380 KB Output is correct
13 Correct 18 ms 22876 KB Output is correct
14 Correct 18 ms 22872 KB Output is correct
15 Correct 18 ms 22876 KB Output is correct
16 Correct 14 ms 22620 KB Output is correct
17 Correct 20 ms 23992 KB Output is correct
18 Correct 17 ms 23896 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 780 ms 92600 KB Output is correct
2 Correct 772 ms 92656 KB Output is correct
3 Correct 725 ms 92660 KB Output is correct
4 Correct 607 ms 131284 KB Output is correct
5 Correct 441 ms 90816 KB Output is correct
6 Correct 517 ms 127232 KB Output is correct
7 Correct 779 ms 92360 KB Output is correct
8 Correct 730 ms 91608 KB Output is correct
9 Correct 683 ms 91588 KB Output is correct
10 Correct 337 ms 90820 KB Output is correct
11 Correct 575 ms 140836 KB Output is correct
12 Correct 1008 ms 136480 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 780 ms 92600 KB Output is correct
2 Correct 772 ms 92656 KB Output is correct
3 Correct 725 ms 92660 KB Output is correct
4 Correct 607 ms 131284 KB Output is correct
5 Correct 441 ms 90816 KB Output is correct
6 Correct 517 ms 127232 KB Output is correct
7 Correct 779 ms 92360 KB Output is correct
8 Correct 730 ms 91608 KB Output is correct
9 Correct 683 ms 91588 KB Output is correct
10 Correct 337 ms 90820 KB Output is correct
11 Correct 575 ms 140836 KB Output is correct
12 Correct 1008 ms 136480 KB Output is correct
13 Correct 861 ms 95132 KB Output is correct
14 Correct 851 ms 94388 KB Output is correct
15 Correct 737 ms 92800 KB Output is correct
16 Correct 767 ms 132808 KB Output is correct
17 Correct 544 ms 92228 KB Output is correct
18 Correct 502 ms 127152 KB Output is correct
19 Correct 826 ms 95032 KB Output is correct
20 Correct 847 ms 94716 KB Output is correct
21 Correct 828 ms 94924 KB Output is correct
22 Correct 346 ms 90828 KB Output is correct
23 Correct 659 ms 140916 KB Output is correct
24 Correct 992 ms 136784 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19288 KB Output is correct
2 Correct 8 ms 19292 KB Output is correct
3 Correct 8 ms 19208 KB Output is correct
4 Correct 9 ms 19292 KB Output is correct
5 Correct 8 ms 19288 KB Output is correct
6 Correct 8 ms 19288 KB Output is correct
7 Correct 22 ms 23028 KB Output is correct
8 Correct 20 ms 22876 KB Output is correct
9 Correct 20 ms 22872 KB Output is correct
10 Correct 20 ms 23896 KB Output is correct
11 Correct 18 ms 22980 KB Output is correct
12 Correct 21 ms 23380 KB Output is correct
13 Correct 18 ms 22876 KB Output is correct
14 Correct 18 ms 22872 KB Output is correct
15 Correct 18 ms 22876 KB Output is correct
16 Correct 14 ms 22620 KB Output is correct
17 Correct 20 ms 23992 KB Output is correct
18 Correct 17 ms 23896 KB Output is correct
19 Correct 780 ms 92600 KB Output is correct
20 Correct 772 ms 92656 KB Output is correct
21 Correct 725 ms 92660 KB Output is correct
22 Correct 607 ms 131284 KB Output is correct
23 Correct 441 ms 90816 KB Output is correct
24 Correct 517 ms 127232 KB Output is correct
25 Correct 779 ms 92360 KB Output is correct
26 Correct 730 ms 91608 KB Output is correct
27 Correct 683 ms 91588 KB Output is correct
28 Correct 337 ms 90820 KB Output is correct
29 Correct 575 ms 140836 KB Output is correct
30 Correct 1008 ms 136480 KB Output is correct
31 Correct 861 ms 95132 KB Output is correct
32 Correct 851 ms 94388 KB Output is correct
33 Correct 737 ms 92800 KB Output is correct
34 Correct 767 ms 132808 KB Output is correct
35 Correct 544 ms 92228 KB Output is correct
36 Correct 502 ms 127152 KB Output is correct
37 Correct 826 ms 95032 KB Output is correct
38 Correct 847 ms 94716 KB Output is correct
39 Correct 828 ms 94924 KB Output is correct
40 Correct 346 ms 90828 KB Output is correct
41 Correct 659 ms 140916 KB Output is correct
42 Correct 992 ms 136784 KB Output is correct
43 Correct 972 ms 96452 KB Output is correct
44 Correct 965 ms 96308 KB Output is correct
45 Correct 952 ms 96292 KB Output is correct
46 Correct 813 ms 139756 KB Output is correct
47 Correct 575 ms 94644 KB Output is correct
48 Correct 562 ms 127052 KB Output is correct
49 Correct 1045 ms 96172 KB Output is correct
50 Correct 884 ms 93120 KB Output is correct
51 Correct 907 ms 93008 KB Output is correct
52 Correct 490 ms 94648 KB Output is correct
53 Correct 1108 ms 143764 KB Output is correct