QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #664073 | #7154. Inflation | Warinchai_s# | 19 | 95ms | 16852kb | C++14 | 1.8kb | 2024-10-21 19:07:57 | 2024-10-21 19:07:57 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q;
struct fenwick{
long long sum[300005];
void upd(int id,long long val){
for(int i=id;i<=300005;i+=i&-i)sum[i]+=val;
}
long long fans(int id){
long long ans=0;
for(int i=id;i>0;i-=i&-i){
ans+=sum[i];
}
return ans;
}
}fw;
long long tlz=0;
long long ar[300005];
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n;
vector<int>v;
vector<pair<int,pair<int,int>>>qr;
for(int i=1;i<=n;i++){
cin>>ar[i];
v.push_back(ar[i]);
}
cin>>q;
for(int i=0;i<q;i++){
string s;cin>>s;
int t,a,b;t=a=b=0;
if(s=="INFLATION"){
t=0;
cin>>a;
tlz+=a;
}else{
t=1;
cin>>a>>b;
v.push_back(b-tlz);
}
qr.push_back({t,{a,b}});
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
tlz=0;
for(int i=1;i<=n;i++){
int id=lower_bound(v.begin(),v.end(),ar[i])-v.begin()+1;
fw.upd(id,ar[i]);
}
for(auto x:qr){
if(x.first==0){
tlz+=x.second.first;
cout<<fw.fans(v.size()+1)+tlz*n<<"\n";
}else{
long long vx=x.second.first-tlz;
long long vy=x.second.second-tlz;
int idx=lower_bound(v.begin(),v.end(),vx)-v.begin()+1;
int idy=lower_bound(v.begin(),v.end(),vy)-v.begin()+1;
/*if(idx-1<v.size()&&vx==v[idx-1]){
long long prev=fw.fans(idx)-fw.fans(idx-1);
fw.upd(idx,-prev);
fw.upd(idy,vy*(prev/vx));
}
cout<<fw.fans(v.size()+1)+tlz*n<<"\n";*/
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 5872kb
input:
1 23 100 INFLATION 65 INFLATION 37 INFLATION 28 INFLATION 41 INFLATION 53 INFLATION 46 SET 81 22 INFLATION 91 SET 45 85 SET 85 14 INFLATION 58 INFLATION 89 SET 98 60 INFLATION 75 INFLATION 97 SET 91 53 INFLATION 31 INFLATION 51 SET 81 78 SET 16 78 INFLATION 59 SET 10 74 INFLATION 55 SET 7 50 INFLATI...
output:
88 125 153 194 247 293 384 442 531 606 703 734 785 844 899 948 974 1005 1089 1105 1162 1219 1303 1308 1337 1353 1374 1407 1456 1474 1492 1571 1658 1730 1797 1896 1939 2033 2057 2077 2106 2185 2228 2312 2353 2446 2544 2638 2667 2712 2774 2833 2876 2947 3044 3075 3138 3147 3189 3286 3319 3344 3442 351...
result:
wrong answer 7th numbers differ - expected: '293', found: '384'
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 0ms
memory: 5944kb
input:
1 23 100 INFLATION 65 INFLATION 37 INFLATION 28 INFLATION 41 INFLATION 53 INFLATION 46 SET 81 22 INFLATION 91 SET 45 85 SET 85 14 INFLATION 58 INFLATION 89 SET 98 60 INFLATION 75 INFLATION 97 SET 91 53 INFLATION 31 INFLATION 51 SET 81 78 SET 16 78 INFLATION 59 SET 10 74 INFLATION 55 SET 7 50 INFLATI...
output:
88 125 153 194 247 293 384 442 531 606 703 734 785 844 899 948 974 1005 1089 1105 1162 1219 1303 1308 1337 1353 1374 1407 1456 1474 1492 1571 1658 1730 1797 1896 1939 2033 2057 2077 2106 2185 2228 2312 2353 2446 2544 2638 2667 2712 2774 2833 2876 2947 3044 3075 3138 3147 3189 3286 3319 3344 3442 351...
result:
wrong answer 7th numbers differ - expected: '293', found: '384'
Subtask #3:
score: 19
Accepted
Test #22:
score: 19
Accepted
time: 85ms
memory: 15360kb
input:
300000 951351 399077 631051 774844 106866 983747 985797 551211 280105 755685 239394 499384 426078 235060 496603 342116 956581 934742 542102 616510 709067 207632 690607 166356 733456 276205 265791 82499 190425 231230 882006 759975 728793 539410 543318 537385 857482 886000 862880 438199 937944 615644 ...
output:
392965539146 675775239146 814176639146 974046639146 1145572239146 1277367339146 1556017839146 1750549839146 1880621439146 2179876239146 2188536939146 2219483439146 2344590639146 2550157539146 2608144839146 2757664539146 2854521339146 3119311839146 3366236139146 3639235239146 3925919739146 4191075039...
result:
ok 100000 numbers
Test #23:
score: 19
Accepted
time: 65ms
memory: 15580kb
input:
300000 8260 5218 6200 7194 4744 7153 45 4146 2619 7974 847 7550 2297 7235 6203 577 1286 5156 8131 831 4093 6302 9500 3826 3162 5486 4286 9348 9575 2862 9270 1771 8006 6341 181 8149 7338 1803 918 6989 3290 5033 6692 5520 2465 941 7173 5839 4939 2055 3653 2126 4738 7435 1976 9048 6690 2854 5091 3598 2...
output:
2605785375 4399485375 5759685375 6541485375 8954385375 10950885375 13432785375 16266585375 16637685375 17009685375 18515085375 19884885375 20803485375 21097185375 22032885375 24453585375 25363485375 25745385375 27074385375 29674185375 31426185375 34337685375 35240085375 37783785375 40687185375 41079...
result:
ok 100000 numbers
Test #24:
score: 19
Accepted
time: 41ms
memory: 14920kb
input:
300000 8 9 58 58 61 70 52 40 18 73 86 54 89 26 7 19 90 55 48 66 33 62 5 39 17 73 70 88 93 4 17 75 93 89 7 84 42 29 6 78 8 7 87 92 2 89 37 88 22 94 42 80 56 41 97 22 68 71 46 53 60 46 4 67 30 23 36 63 24 43 35 88 93 6 72 10 61 64 85 31 5 38 38 85 13 100 2 48 73 49 56 50 86 16 43 3 2 45 65 49 82 48 34...
output:
36749958 60449958 88949958 102749958 113249958 133349958 156449958 175649958 204149958 220949958 247649958 251849958 254549958 276149958 285449958 297749958 314849958 340349958 346049958 362849958 365549958 368849958 398549958 419549958 421049958 429149958 449249958 469949958 490349958 499649958 507...
result:
ok 100000 numbers
Test #25:
score: 19
Accepted
time: 27ms
memory: 14104kb
input:
300000 5 4 7 10 4 10 10 6 10 2 5 6 5 9 9 4 5 2 6 2 5 4 7 10 7 6 9 3 6 3 3 2 4 8 10 3 1 10 7 5 1 7 1 3 1 8 4 3 4 2 1 6 1 10 6 2 7 1 1 7 7 5 9 3 10 1 1 9 3 4 7 4 3 8 5 10 4 6 3 7 1 7 3 6 9 9 6 3 5 5 8 6 2 3 6 2 7 3 9 5 7 1 9 8 9 10 7 1 2 10 7 2 2 5 5 2 5 4 6 6 7 3 7 1 4 2 9 2 9 9 6 1 3 5 8 2 5 4 8 7 3...
output:
3748987 4648987 6148987 7048987 7648987 8848987 11248987 14248987 15448987 16648987 18448987 19948987 21748987 22348987 24448987 27148987 28948987 30448987 33448987 33748987 36748987 38248987 38548987 40948987 43348987 46048987 47248987 48748987 49648987 49948987 52648987 53548987 54148987 55048987 ...
result:
ok 100000 numbers
Test #26:
score: 19
Accepted
time: 26ms
memory: 16852kb
input:
300000 2 2 1 2 1 1 2 2 1 2 1 2 1 2 2 1 2 2 1 1 1 2 2 2 2 1 2 2 1 2 1 2 2 2 2 1 1 1 1 2 1 1 2 1 2 1 1 2 2 2 2 2 1 2 1 2 1 2 1 1 1 2 1 1 2 2 2 2 2 1 2 2 2 1 1 2 2 2 2 1 1 2 2 2 1 2 1 2 2 2 2 1 1 2 1 1 1 2 1 1 1 1 1 1 1 1 2 2 1 2 2 1 1 1 1 1 1 2 1 2 2 2 2 1 2 1 1 1 2 1 2 1 2 1 2 2 2 2 2 2 2 1 1 2 2 2 2...
output:
1049646 1649646 2249646 2549646 2849646 3149646 3449646 4049646 4349646 4949646 5549646 6149646 6449646 6749646 7049646 7349646 7649646 7949646 8249646 8549646 8849646 9149646 9449646 9749646 10349646 10949646 11549646 11849646 12149646 12449646 13049646 13349646 13649646 14249646 14849646 15449646 ...
result:
ok 100000 numbers
Test #27:
score: 19
Accepted
time: 41ms
memory: 15200kb
input:
300000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 10000...
output:
600000000000 900000000000 1200000000000 1500000000000 1800000000000 2100000000000 2400000000000 2700000000000 3000000000000 3300000000000 3600000000000 3900000000000 4200000000000 4500000000000 4800000000000 5100000000000 5400000000000 5700000000000 6000000000000 6300000000000 6600000000000 69000000...
result:
ok 100000 numbers
Subtask #4:
score: 0
Wrong Answer
Test #28:
score: 0
Wrong Answer
time: 95ms
memory: 16656kb
input:
300000 947318 850376 902969 604347 67162 326934 983509 617741 797556 532417 364000 987510 494945 673154 690612 243955 959719 909872 189543 627965 826065 586321 119252 290670 655680 527058 254003 559766 354780 659156 812403 214395 771905 87515 353059 677708 142575 286504 122078 61221 239279 348056 55...
output:
result:
wrong answer Answer contains longer sequence [length = 100000], but output contains 0 elements
Subtask #5:
score: 0
Wrong Answer
Test #37:
score: 0
Wrong Answer
time: 1ms
memory: 5644kb
input:
1 23 100 INFLATION 65 INFLATION 37 INFLATION 28 INFLATION 41 INFLATION 53 INFLATION 46 SET 81 22 INFLATION 91 SET 45 85 SET 85 14 INFLATION 58 INFLATION 89 SET 98 60 INFLATION 75 INFLATION 97 SET 91 53 INFLATION 31 INFLATION 51 SET 81 78 SET 16 78 INFLATION 59 SET 10 74 INFLATION 55 SET 7 50 INFLATI...
output:
88 125 153 194 247 293 384 442 531 606 703 734 785 844 899 948 974 1005 1089 1105 1162 1219 1303 1308 1337 1353 1374 1407 1456 1474 1492 1571 1658 1730 1797 1896 1939 2033 2057 2077 2106 2185 2228 2312 2353 2446 2544 2638 2667 2712 2774 2833 2876 2947 3044 3075 3138 3147 3189 3286 3319 3344 3442 351...
result:
wrong answer 7th numbers differ - expected: '293', found: '384'