oj.uz

Submission #921483

# Submission time Handle Problem Language Result Execution time Memory
921483 2024-02-04T01:51:47 Z 1075508020060209tc Examination (JOI19_examination) C++14
100 / 100
 1203 ms 57848 KB 
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
#define SZ(x) (int)(x).size()
int lowbit(int x){return x&-x;}
int bit[1000006];
void upd(int pl,int x){
while(pl<=1000000){
    bit[pl]+=x;
    pl+=lowbit(pl);
}
}
int qsum(int pl){
int ret=0;
while(pl>=1){
    ret+=bit[pl];
    pl-=lowbit(pl);
}
return ret;
}
int n;int Q;
int ar[200005];int br[200005];int cr[200005];
int idar[200005];
int tar[200005];
void lisanhua(){
vector<int>vc;
for(int i=1;i<=n+Q;i++){
    vc.push_back(ar[i]);
    vc.push_back(br[i]);
    vc.push_back(cr[i]);
}
sort(vc.begin(),vc.end());
int it=2;
map<int,int>mp;
mp[vc[0]]=it;
for(int i=1;i<vc.size();i++){
    if(vc[i]!=vc[i-1]){
        mp[vc[i]]=++it;
    }
}
for(int i=1;i<=n+Q;i++){
    ar[i]=mp[ar[i]];
    br[i]=mp[br[i]];
    cr[i]=mp[cr[i]];
}
}


bool cmp(int i,int j){
if(ar[i]<ar[j]){return 1;}
if(ar[i]>ar[j]){return 0;}
return i<j;
}
int ans[200005];
void cdq(int l,int r){
if(l==r){return;}
int mi=(l+r)/2;
cdq(l,mi);cdq(mi+1,r);
int rit=r;
int lit=mi;
vector<int>vc;
for(int i=r;i>=l;i--){
    if( (lit<l)||(rit>=mi+1&&br[idar[rit]]>br[idar[lit]]) ){
        tar[i]=idar[rit--];
        if(tar[i]<=n){
            upd(cr[tar[i]],1);
            vc.push_back(cr[tar[i]]);
        }
    }else{
        tar[i]=idar[lit--];
        ans[tar[i]]+=qsum(1000000)-qsum(cr[tar[i]]);
    }
}

for(int i=0;i<vc.size();i++){
    upd(vc[i],-1);
}

for(int i=l;i<=r;i++){
    idar[i]=tar[i];
}
}


signed main(){

cin>>n>>Q;
for(int i=1;i<=n;i++){
    cin>>ar[i]>>br[i];
    cr[i]=ar[i]+br[i];
}
for(int i=1;i<=Q;i++){
    cin>>ar[i+n]>>br[i+n]>>cr[i+n];
    ar[i+n]--;
    br[i+n]--;
    cr[i+n]--;
}
lisanhua();
for(int i=1;i<=n+Q;i++){
    idar[i]=i;
}

sort(idar+1,idar+n+Q+1,cmp);
cdq(1,n+Q);
for(int i=n+1;i<=n+Q;i++){
    cout<<ans[i]<<"\n";
}return 0;
for(int i=1;i<=n+Q;i++){
    cout<<idar[i]<<" ";
}

}

Compilation message

examination.cpp: In function 'void lisanhua()':
examination.cpp:39:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 | for(int i=1;i<vc.size();i++){
      |             ~^~~~~~~~~~
examination.cpp: In function 'void cdq(long long int, long long int)':
examination.cpp:78:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 | for(int i=0;i<vc.size();i++){
      |             ~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12732 KB Output is correct
7 Correct 17 ms 14052 KB Output is correct
8 Correct 15 ms 13896 KB Output is correct
9 Correct 16 ms 14032 KB Output is correct
10 Correct 13 ms 13640 KB Output is correct
11 Correct 13 ms 13640 KB Output is correct
12 Correct 8 ms 12988 KB Output is correct
13 Correct 14 ms 13896 KB Output is correct
14 Correct 14 ms 13896 KB Output is correct
15 Correct 14 ms 15912 KB Output is correct
16 Correct 10 ms 13124 KB Output is correct
17 Correct 11 ms 13384 KB Output is correct
18 Correct 8 ms 12872 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 21908 KB Output is correct
2 Correct 446 ms 24416 KB Output is correct
3 Correct 450 ms 24484 KB Output is correct
4 Correct 319 ms 21068 KB Output is correct
5 Correct 334 ms 21104 KB Output is correct
6 Correct 224 ms 17684 KB Output is correct
7 Correct 404 ms 24220 KB Output is correct
8 Correct 439 ms 26260 KB Output is correct
9 Correct 398 ms 24052 KB Output is correct
10 Correct 304 ms 20444 KB Output is correct
11 Correct 314 ms 22476 KB Output is correct
12 Correct 232 ms 17300 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 21908 KB Output is correct
2 Correct 446 ms 24416 KB Output is correct
3 Correct 450 ms 24484 KB Output is correct
4 Correct 319 ms 21068 KB Output is correct
5 Correct 334 ms 21104 KB Output is correct
6 Correct 224 ms 17684 KB Output is correct
7 Correct 404 ms 24220 KB Output is correct
8 Correct 439 ms 26260 KB Output is correct
9 Correct 398 ms 24052 KB Output is correct
10 Correct 304 ms 20444 KB Output is correct
11 Correct 314 ms 22476 KB Output is correct
12 Correct 232 ms 17300 KB Output is correct
13 Correct 491 ms 25012 KB Output is correct
14 Correct 482 ms 26724 KB Output is correct
15 Correct 429 ms 24352 KB Output is correct
16 Correct 383 ms 21716 KB Output is correct
17 Correct 383 ms 21692 KB Output is correct
18 Correct 234 ms 17436 KB Output is correct
19 Correct 510 ms 28420 KB Output is correct
20 Correct 513 ms 27492 KB Output is correct
21 Correct 484 ms 26336 KB Output is correct
22 Correct 304 ms 20220 KB Output is correct
23 Correct 298 ms 20212 KB Output is correct
24 Correct 232 ms 17344 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12732 KB Output is correct
7 Correct 17 ms 14052 KB Output is correct
8 Correct 15 ms 13896 KB Output is correct
9 Correct 16 ms 14032 KB Output is correct
10 Correct 13 ms 13640 KB Output is correct
11 Correct 13 ms 13640 KB Output is correct
12 Correct 8 ms 12988 KB Output is correct
13 Correct 14 ms 13896 KB Output is correct
14 Correct 14 ms 13896 KB Output is correct
15 Correct 14 ms 15912 KB Output is correct
16 Correct 10 ms 13124 KB Output is correct
17 Correct 11 ms 13384 KB Output is correct
18 Correct 8 ms 12872 KB Output is correct
19 Correct 421 ms 21908 KB Output is correct
20 Correct 446 ms 24416 KB Output is correct
21 Correct 450 ms 24484 KB Output is correct
22 Correct 319 ms 21068 KB Output is correct
23 Correct 334 ms 21104 KB Output is correct
24 Correct 224 ms 17684 KB Output is correct
25 Correct 404 ms 24220 KB Output is correct
26 Correct 439 ms 26260 KB Output is correct
27 Correct 398 ms 24052 KB Output is correct
28 Correct 304 ms 20444 KB Output is correct
29 Correct 314 ms 22476 KB Output is correct
30 Correct 232 ms 17300 KB Output is correct
31 Correct 491 ms 25012 KB Output is correct
32 Correct 482 ms 26724 KB Output is correct
33 Correct 429 ms 24352 KB Output is correct
34 Correct 383 ms 21716 KB Output is correct
35 Correct 383 ms 21692 KB Output is correct
36 Correct 234 ms 17436 KB Output is correct
37 Correct 510 ms 28420 KB Output is correct
38 Correct 513 ms 27492 KB Output is correct
39 Correct 484 ms 26336 KB Output is correct
40 Correct 304 ms 20220 KB Output is correct
41 Correct 298 ms 20212 KB Output is correct
42 Correct 232 ms 17344 KB Output is correct
43 Correct 1153 ms 57272 KB Output is correct
44 Correct 1083 ms 57368 KB Output is correct
45 Correct 1122 ms 57464 KB Output is correct
46 Correct 627 ms 41076 KB Output is correct
47 Correct 637 ms 41152 KB Output is correct
48 Correct 237 ms 17008 KB Output is correct
49 Correct 1203 ms 57804 KB Output is correct
50 Correct 1140 ms 57848 KB Output is correct
51 Correct 1042 ms 57240 KB Output is correct
52 Correct 555 ms 34988 KB Output is correct
53 Correct 401 ms 28396 KB Output is correct