Submission #1442227
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef signed long long ll; #undef _P #define _P(...) (void)printf(__VA_ARGS__) #define FOR(x,to) for(x=0;x<(to);x++) #define FORR(x,arr) for(auto& x:arr) #define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++) #define ALL(a) (a.begin()),(a.end()) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) //------------------------------------------------------- int N,Q; ll W[101010],T[101010],X[101010]; ll add[3][3710000]; int day[101010]; ll num[4000000]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>Q; priority_queue<pair<ll,int>> P; FOR(i,N) { cin>>W[i]>>T[i]>>X[i]; P.push({-W[i],i}); } ll cur[3]={}; ll tot=0; for(i=0;i<=3700000;i++) { tot += cur[0] + cur[1]*i + cur[2]*i*i; if(i==0) cur[0]++; num[i]=tot; while(P.size() && tot>=-P.top().first) { x = P.top().second; P.pop(); day[x]=i; num[i]++; if(T[x]==0) { cur[0]++; add[0][i+X[x]]--; } else if(T[x]==1) { cur[0]-=i; add[0][i+X[x]]+=i; cur[1]++; add[1][i+X[x]]--; } else if(T[x]==2) { cur[0]+=1LL*i*i; add[0][i+X[x]]-=1LL*i*i; cur[1]-=2LL*i; add[1][i+X[x]]+=2LL*i; cur[2]++; add[2][i+X[x]]--; } } cur[0]+=add[0][i]; cur[1]+=add[1][i]; cur[2]+=add[2][i]; } FOR(i,N) { if(day[i]==0 || day[i]>3652425) cout<<"Many years later"<<endl; else cout<<day[i]<<endl; } FOR(i,Q) { cin>>x; cout<<num[x]<<endl; } } int main(int argc,char** argv){ string s;int i; if(argc==1) ios::sync_with_stdio(false), cin.tie(0); FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin); solve(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Acceleration of Network |
User | kmjp |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1792 Byte |
Status | WA |
Exec Time | 356 ms |
Memory | 45424 KB |
Judge Result
Set Name | Partial 1 | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 15 | 0 / 85 | ||||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Partial 1 | 0_00_sample_00, 0_10_Random_00_000000_000265, 0_10_Random_01_001000_000265, 0_10_Random_02_001000_000263, 0_10_Random_03_000003_000251, 0_10_Random_04_000003_000261, 0_10_Random_05_000003_000257, 0_10_Random_06_000009_000251, 0_10_Random_07_000000_000262, 0_10_Random_08_000000_000256, 0_10_Random_09_000003_000262, 0_10_Random_10_000002_000261, 0_10_Random_11_000006_000255, 0_10_Random_12_000004_000253, 0_10_Random_13_000054_000262, 0_10_Random_14_000033_000265, 0_10_Random_15_000052_000253, 0_10_Random_16_000000_000259, 0_10_Random_17_000078_000253, 0_10_Random_18_000417_000254, 0_10_Random_19_000417_000254, 0_10_Random_20_000913_000259, 0_10_Random_21_000238_000255, 0_10_Random_22_000335_000255 |
All | 0_00_sample_00, 0_10_Random_00_000000_000265, 0_10_Random_01_001000_000265, 0_10_Random_02_001000_000263, 0_10_Random_03_000003_000251, 0_10_Random_04_000003_000261, 0_10_Random_05_000003_000257, 0_10_Random_06_000009_000251, 0_10_Random_07_000000_000262, 0_10_Random_08_000000_000256, 0_10_Random_09_000003_000262, 0_10_Random_10_000002_000261, 0_10_Random_11_000006_000255, 0_10_Random_12_000004_000253, 0_10_Random_13_000054_000262, 0_10_Random_14_000033_000265, 0_10_Random_15_000052_000253, 0_10_Random_16_000000_000259, 0_10_Random_17_000078_000253, 0_10_Random_18_000417_000254, 0_10_Random_19_000417_000254, 0_10_Random_20_000913_000259, 0_10_Random_21_000238_000255, 0_10_Random_22_000335_000255, 1_00_sample_01, 1_00_sample_02, 1_01_Teuchi_00, 1_01_Teuchi_01, 1_01_Teuchi_02, 1_01_Teuchi_03, 1_10_Random_23_086198_063414, 1_10_Random_24_041759_025278, 1_10_Random_25_078163_017646, 1_10_Random_26_082466_052832, 1_10_Random_27_069483_058001, 1_10_Random_28_037260_074459, 1_10_Random_29_094251_071690, 1_10_Random_30_080555_029493, 1_10_Random_31_099897_068369, 1_10_Random_32_086928_020563, 1_10_Random_33_019288_027448, 1_10_Random_34_027325_013687, 1_10_Random_35_037565_046230, 1_10_Random_36_053110_007707, 1_10_Random_37_006561_051152, 1_10_Random_38_001724_008865, 1_10_Random_39_075823_030498, 1_10_Random_40_035920_003446, 1_10_Random_41_061129_090693, 1_10_Random_42_026102_061986, 1_20_HalfRandom_00_033145_012808, 1_20_HalfRandom_01_051361_052902, 1_20_HalfRandom_02_072789_061928, 1_20_HalfRandom_03_080965_031006, 1_20_HalfRandom_04_039937_038308, 1_20_HalfRandom_05_098476_067390, 1_20_HalfRandom_06_061198_009066, 1_20_HalfRandom_07_096374_098697, 1_20_HalfRandom_08_077042_019386, 1_20_HalfRandom_09_023570_047790 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_00_sample_00 | WA | 21 ms | 41216 KB |
0_10_Random_00_000000_000265 | AC | 19 ms | 30976 KB |
0_10_Random_01_001000_000265 | WA | 23 ms | 41216 KB |
0_10_Random_02_001000_000263 | WA | 23 ms | 41216 KB |
0_10_Random_03_000003_000251 | WA | 20 ms | 37120 KB |
0_10_Random_04_000003_000261 | WA | 20 ms | 39168 KB |
0_10_Random_05_000003_000257 | WA | 22 ms | 41216 KB |
0_10_Random_06_000009_000251 | WA | 21 ms | 41216 KB |
0_10_Random_07_000000_000262 | AC | 19 ms | 30976 KB |
0_10_Random_08_000000_000256 | AC | 19 ms | 30976 KB |
0_10_Random_09_000003_000262 | WA | 21 ms | 41344 KB |
0_10_Random_10_000002_000261 | WA | 21 ms | 41216 KB |
0_10_Random_11_000006_000255 | WA | 21 ms | 41216 KB |
0_10_Random_12_000004_000253 | WA | 21 ms | 41216 KB |
0_10_Random_13_000054_000262 | WA | 21 ms | 41216 KB |
0_10_Random_14_000033_000265 | WA | 21 ms | 41216 KB |
0_10_Random_15_000052_000253 | AC | 21 ms | 41216 KB |
0_10_Random_16_000000_000259 | AC | 19 ms | 30976 KB |
0_10_Random_17_000078_000253 | WA | 21 ms | 41216 KB |
0_10_Random_18_000417_000254 | AC | 22 ms | 41216 KB |
0_10_Random_19_000417_000254 | WA | 22 ms | 41216 KB |
0_10_Random_20_000913_000259 | WA | 22 ms | 41216 KB |
0_10_Random_21_000238_000255 | WA | 21 ms | 41216 KB |
0_10_Random_22_000335_000255 | WA | 21 ms | 41216 KB |
1_00_sample_01 | WA | 20 ms | 41216 KB |
1_00_sample_02 | WA | 22 ms | 41216 KB |
1_01_Teuchi_00 | WA | 206 ms | 43888 KB |
1_01_Teuchi_01 | WA | 197 ms | 44656 KB |
1_01_Teuchi_02 | AC | 19 ms | 30976 KB |
1_01_Teuchi_03 | WA | 200 ms | 44656 KB |
1_10_Random_23_086198_063414 | WA | 284 ms | 43888 KB |
1_10_Random_24_041759_025278 | WA | 135 ms | 42484 KB |
1_10_Random_25_078163_017646 | WA | 188 ms | 42992 KB |
1_10_Random_26_082466_052832 | WA | 255 ms | 43760 KB |
1_10_Random_27_069483_058001 | WA | 240 ms | 43504 KB |
1_10_Random_28_037260_074459 | WA | 221 ms | 43124 KB |
1_10_Random_29_094251_071690 | WA | 306 ms | 44144 KB |
1_10_Random_30_080555_029493 | WA | 211 ms | 43248 KB |
1_10_Random_31_099897_068369 | WA | 309 ms | 44400 KB |
1_10_Random_32_086928_020563 | WA | 209 ms | 43248 KB |
1_10_Random_33_019288_027448 | AC | 101 ms | 42232 KB |
1_10_Random_34_027325_013687 | WA | 95 ms | 42104 KB |
1_10_Random_35_037565_046230 | WA | 163 ms | 42740 KB |
1_10_Random_36_053110_007707 | AC | 130 ms | 42612 KB |
1_10_Random_37_006561_051152 | WA | 117 ms | 42240 KB |
1_10_Random_38_001724_008865 | WA | 39 ms | 43392 KB |
1_10_Random_39_075823_030498 | WA | 210 ms | 43376 KB |
1_10_Random_40_035920_003446 | AC | 92 ms | 42228 KB |
1_10_Random_41_061129_090693 | WA | 279 ms | 43892 KB |
1_10_Random_42_026102_061986 | WA | 170 ms | 42744 KB |
1_20_HalfRandom_00_033145_012808 | WA | 104 ms | 44276 KB |
1_20_HalfRandom_01_051361_052902 | WA | 200 ms | 43124 KB |
1_20_HalfRandom_02_072789_061928 | WA | 256 ms | 43760 KB |
1_20_HalfRandom_03_080965_031006 | WA | 216 ms | 43760 KB |
1_20_HalfRandom_04_039937_038308 | WA | 154 ms | 42868 KB |
1_20_HalfRandom_05_098476_067390 | WA | 308 ms | 44784 KB |
1_20_HalfRandom_06_061198_009066 | WA | 145 ms | 42996 KB |
1_20_HalfRandom_07_096374_098697 | WA | 356 ms | 45424 KB |
1_20_HalfRandom_08_077042_019386 | WA | 188 ms | 43504 KB |
1_20_HalfRandom_09_023570_047790 | WA | 144 ms | 42616 KB |