QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#438729#8590. Problem Settergiorgi_pkhaladze0 167ms18640kbC++23894b2024-06-11 01:38:452024-06-11 01:38:46

Judging History

你现在查看的是最新测评结果

  • [2024-06-11 01:38:46]
  • 评测
  • 测评结果:0
  • 用时:167ms
  • 内存:18640kb
  • [2024-06-11 01:38:45]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
using namespace std;
int n,m,k,i,j,ans;
vector<int> t(4*1000005);
void update(int v,int l,int r,int pos,int x){
    if(l==r){t[v]=max(t[v], x); return; }
    int m=(l+r)/2;
    if(pos<=m)update(v*2,l,m,pos,x);
    else update(v*2+1,m+1,r,pos,x);
    t[v]=max(t[v*2],t[v*2+1]);
}
int mn(int v, int tl, int tr, int l, int r){
    if(tl>r || tr<l) return 0;
    if(l<=tl && tr<=r)return t[v];
    int m=(tl+tr)/2;
    return max(mn(v*2,l,m,l,r),mn(v*2+1,m+1,r,l,r));
}
int main() {
cin>>n>>m;
for(k=1; k<=n; k++){
    cin>>i>>j;
    update(1,1,1000000,i,j);
}
//cout<<1; return 0;
t.resize(4*n+5,0);
while(m--){
    int x,y;
    cin>>x>>y;
    ans+=max(0,mn(1,1,1000000,1,x)-y);
}
cout<<ans;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 18
Accepted
time: 0ms
memory: 18484kb

input:

1000 1
570339 324084
75781 292531
427864 843267
928484 613828
883296 385343
733451 782070
756314 89477
786410 133722
455015 841750
146307 536680
992681 107898
657731 633895
764691 258779
142935 640379
445046 717170
227758 578083
526095 660806
859673 757597
898726 4088
719881 887973
850810 674331
752...

output:

575102

result:

ok single line: '575102'

Test #2:

score: -18
Wrong Answer
time: 0ms
memory: 18640kb

input:

1000 1
93555 337906
136252 661901
127242 762569
370437 288257
767189 41343
788899 716075
654667 69573
991915 927883
7763 509983
986424 963695
362599 476740
955459 125250
620759 316409
611815 579388
450941 792473
270525 969538
184881 646954
624056 237034
592281 938786
454775 905658
805770 146630
6691...

output:

267027

result:

wrong answer 1st lines differ - expected: '266314', found: '267027'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #24:

score: 0
Wrong Answer
time: 167ms
memory: 18580kb

input:

200000 200000
443848 257048
353855 430518
112240 460358
489050 850745
18217 643349
796031 335731
553602 81823
556808 39341
963397 797473
713023 273372
888193 500234
801660 980841
416233 163140
649254 659678
434013 461662
805451 259446
107168 839690
438518 100393
584335 435627
735040 11809
906814 672...

output:

-1873715601

result:

wrong answer 1st lines differ - expected: '199985649927', found: '-1873715601'

Subtask #4:

score: 0
Skipped

Dependency #1:

0%