Submission #1442238
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; FOR(i,N) cin>>W[i]>>T[i]>>X[i]; ll cur[3]={}; ll tot=0; int did=0; MINUS(day); for(i=0;i<=3700000;i++) { tot += cur[0] + cur[1]*i + cur[2]*i*i; num[i]=tot; while(did<N && tot>=W[did]) { day[did]=i; if(T[did]==0) { cur[0]++; add[0][i+X[did]]--; } else if(T[did]==1) { cur[0]-=i; add[0][i+X[did]]+=i; cur[1]++; add[1][i+X[did]]--; } else if(T[did]==2) { cur[0]+=1LL*i*i; add[0][i+X[did]]-=1LL*i*i; cur[1]-=2LL*i; add[1][i+X[did]]+=2LL*i; cur[2]++; add[2][i+X[did]]--; } did++; } if(i==0) cur[0]++; 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 | 100 |
Code Size | 1721 Byte |
Status | AC |
Exec Time | 344 ms |
Memory | 43648 KB |
Judge Result
Set Name | Partial 1 | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 15 / 15 | 85 / 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 | AC | 18 ms | 41216 KB |
0_10_Random_00_000000_000265 | AC | 17 ms | 33024 KB |
0_10_Random_01_001000_000265 | AC | 20 ms | 41216 KB |
0_10_Random_02_001000_000263 | AC | 20 ms | 41216 KB |
0_10_Random_03_000003_000251 | AC | 18 ms | 37120 KB |
0_10_Random_04_000003_000261 | AC | 18 ms | 39168 KB |
0_10_Random_05_000003_000257 | AC | 19 ms | 41216 KB |
0_10_Random_06_000009_000251 | AC | 19 ms | 41216 KB |
0_10_Random_07_000000_000262 | AC | 17 ms | 33024 KB |
0_10_Random_08_000000_000256 | AC | 17 ms | 33024 KB |
0_10_Random_09_000003_000262 | AC | 19 ms | 41216 KB |
0_10_Random_10_000002_000261 | AC | 19 ms | 41216 KB |
0_10_Random_11_000006_000255 | AC | 19 ms | 41216 KB |
0_10_Random_12_000004_000253 | AC | 19 ms | 41216 KB |
0_10_Random_13_000054_000262 | AC | 19 ms | 41216 KB |
0_10_Random_14_000033_000265 | AC | 19 ms | 41216 KB |
0_10_Random_15_000052_000253 | AC | 19 ms | 41216 KB |
0_10_Random_16_000000_000259 | AC | 17 ms | 33024 KB |
0_10_Random_17_000078_000253 | AC | 19 ms | 41216 KB |
0_10_Random_18_000417_000254 | AC | 19 ms | 41216 KB |
0_10_Random_19_000417_000254 | AC | 20 ms | 41216 KB |
0_10_Random_20_000913_000259 | AC | 20 ms | 41216 KB |
0_10_Random_21_000238_000255 | AC | 19 ms | 41216 KB |
0_10_Random_22_000335_000255 | AC | 19 ms | 41216 KB |
1_00_sample_01 | AC | 18 ms | 41216 KB |
1_00_sample_02 | AC | 19 ms | 41216 KB |
1_01_Teuchi_00 | AC | 187 ms | 42112 KB |
1_01_Teuchi_01 | AC | 182 ms | 41600 KB |
1_01_Teuchi_02 | AC | 17 ms | 33024 KB |
1_01_Teuchi_03 | AC | 183 ms | 41600 KB |
1_10_Random_23_086198_063414 | AC | 270 ms | 42368 KB |
1_10_Random_24_041759_025278 | AC | 130 ms | 41728 KB |
1_10_Random_25_078163_017646 | AC | 178 ms | 41728 KB |
1_10_Random_26_082466_052832 | AC | 248 ms | 42240 KB |
1_10_Random_27_069483_058001 | AC | 234 ms | 42240 KB |
1_10_Random_28_037260_074459 | AC | 207 ms | 42496 KB |
1_10_Random_29_094251_071690 | AC | 294 ms | 42624 KB |
1_10_Random_30_080555_029493 | AC | 202 ms | 41856 KB |
1_10_Random_31_099897_068369 | AC | 296 ms | 42752 KB |
1_10_Random_32_086928_020563 | AC | 205 ms | 41856 KB |
1_10_Random_33_019288_027448 | AC | 96 ms | 41728 KB |
1_10_Random_34_027325_013687 | AC | 89 ms | 41600 KB |
1_10_Random_35_037565_046230 | AC | 158 ms | 42112 KB |
1_10_Random_36_053110_007707 | AC | 121 ms | 41600 KB |
1_10_Random_37_006561_051152 | AC | 115 ms | 41984 KB |
1_10_Random_38_001724_008865 | AC | 36 ms | 43392 KB |
1_10_Random_39_075823_030498 | AC | 198 ms | 42112 KB |
1_10_Random_40_035920_003446 | AC | 86 ms | 41472 KB |
1_10_Random_41_061129_090693 | AC | 273 ms | 42880 KB |
1_10_Random_42_026102_061986 | AC | 170 ms | 42240 KB |
1_20_HalfRandom_00_033145_012808 | AC | 97 ms | 43648 KB |
1_20_HalfRandom_01_051361_052902 | AC | 191 ms | 42240 KB |
1_20_HalfRandom_02_072789_061928 | AC | 243 ms | 42496 KB |
1_20_HalfRandom_03_080965_031006 | AC | 204 ms | 42368 KB |
1_20_HalfRandom_04_039937_038308 | AC | 154 ms | 42112 KB |
1_20_HalfRandom_05_098476_067390 | AC | 298 ms | 43136 KB |
1_20_HalfRandom_06_061198_009066 | AC | 138 ms | 41856 KB |
1_20_HalfRandom_07_096374_098697 | AC | 344 ms | 43648 KB |
1_20_HalfRandom_08_077042_019386 | AC | 183 ms | 42240 KB |
1_20_HalfRandom_09_023570_047790 | AC | 137 ms | 42112 KB |