Submission #620725
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))
//-------------------------------------------------------
// 参照も更新もrange
template<class V,int NV> class SegTree_3 {
public:
vector<V> val;
vector<int> clean;
SegTree_3(){ val.resize(NV*2); clean.resize(NV*2);}
ll getval(int v,int l=0,int r=NV,int k=1) {
if(r<=v || v<l) return 0;
ll ret=val[k];
if(clean[k]==0 && r-l>=2) ret+=getval(v,l,(l+r)/2,k*2)+getval(v,(l+r)/2,r,k*2+1);
return ret;
}
void add(int x,int y, V v,int l=0,int r=NV,int k=1) {
if(l>=r || x>=y) return;
if(x<=l && r<=y) {
val[k]+=v;
}
else if(l < y && x < r) {
if(clean[k]==1) {
clean[k]=0;
val[2*k]=val[2*k+1]=0;
clean[2*k]=clean[2*k+1]=1;
}
add(x,y,v,l,(l+r)/2,k*2);
add(x,y,v,(l+r)/2,r,k*2+1);
}
}
void clear(int x,int y,int l=0,int r=NV,int k=1) {
if(l>=r || x>=y) return;
if(x<=l && r<=y) {
val[k]=0;
clean[k]=1;
}
else if(l < y && x < r) {
if(clean[k]==1) {
clean[k]=0;
val[2*k]=val[2*k+1]=0;
clean[2*k]=clean[2*k+1]=1;
}
val[2*k]+=val[k];
val[2*k+1]+=val[k];
val[k]=0;
clear(x,y,l,(l+r)/2,k*2);
clear(x,y,(l+r)/2,r,k*2+1);
}
}
};
int N,L,M;
vector<vector<int>> V;
SegTree_3<ll,1<<20> bta,btb;
void solve() {
int i,j,k,l,r,x,y; string s;
cin>>N>>L;
j=0;
FOR(i,N) {
cin>>x>>y;
if(x!=j) j=x,V.push_back(vector<int>());
V.back().push_back(y);
}
ll mix=0, miv=0;
FORR(v,V) {
FORR(r,v) {
//_P("add %d %d\n",r,L);
bta.add(0,r,-1);
bta.add(r+1,L+1,1);
btb.add(0,r,r);
btb.add(r+1,L+1,-r);
}
int LL=0,RR=L;
while(LL+6<=RR) {
int x1=(LL*2+RR)/3;
int x2=(LL+RR*2)/3;
ll v1=bta.getval(x1)*x1+btb.getval(x1);
ll v2=bta.getval(x2)*x2+btb.getval(x2);
if(v1<=v2) RR=x2;
else LL=x1;
}
mix=LL;
miv=bta.getval(mix)*mix+btb.getval(mix);
for(x=LL+1;x<=RR;x++) {
ll v=bta.getval(x)*x+btb.getval(x);
if(v<miv) miv=v,mix=x;
}
/*
FOR(i,L+1) _P("%d:(%lld,%lld:%lld) ",i,bta.getval(i),btb.getval(i),(bta.getval(i)*i+btb.getval(i)));
_P("\n");
_P("mimx : %lld %lld\n",mix,miv);
*/
bta.clear(mix+1,L+1);
btb.clear(mix+1,L+1);
btb.add(mix+1,L+1,miv);
/*
FOR(i,L+1) _P("%d:(%lld,%lld:%lld) ",i,bta.getval(i),btb.getval(i),(bta.getval(i)*i+btb.getval(i)));
_P("\n");
*/
}
cout<<miv<<endl;
}
int main(int argc,char** argv){
string s;int i;
if(argc==1) ios::sync_with_stdio(false);
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 |
E - 花火 |
User |
kmjp |
Language |
C++11 (GCC 4.9.2) |
Score |
160 |
Code Size |
2985 Byte |
Status |
AC |
Exec Time |
2239 ms |
Memory |
55448 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
30 / 30 |
130 / 130 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
Subtask1 |
sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt, subtask1_34.txt, subtask1_35.txt, subtask1_36.txt, subtask1_37.txt, subtask1_38.txt, subtask1_39.txt, subtask1_40.txt, subtask1_41.txt, subtask1_42.txt |
Subtask2 |
sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt, subtask1_34.txt, subtask1_35.txt, subtask1_36.txt, subtask1_37.txt, subtask1_38.txt, subtask1_39.txt, subtask1_40.txt, subtask1_41.txt, subtask1_42.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt, subtask2_30.txt, subtask2_31.txt, subtask2_32.txt, subtask2_33.txt, subtask2_34.txt, subtask2_35.txt, subtask2_36.txt, subtask2_37.txt, subtask2_38.txt, subtask2_39.txt, subtask2_40.txt, subtask2_41.txt, subtask2_42.txt, subtask2_43.txt, subtask2_44.txt, subtask2_45.txt, subtask2_46.txt, subtask2_47.txt, subtask2_48.txt, subtask2_49.txt, subtask2_50.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
137 ms |
49956 KB |
sample_02.txt |
AC |
135 ms |
49952 KB |
sample_03.txt |
AC |
122 ms |
50016 KB |
subtask1_01.txt |
AC |
143 ms |
50028 KB |
subtask1_02.txt |
AC |
143 ms |
50144 KB |
subtask1_03.txt |
AC |
144 ms |
50012 KB |
subtask1_04.txt |
AC |
144 ms |
50024 KB |
subtask1_05.txt |
AC |
125 ms |
50140 KB |
subtask1_06.txt |
AC |
131 ms |
50152 KB |
subtask1_07.txt |
AC |
136 ms |
50148 KB |
subtask1_08.txt |
AC |
138 ms |
50140 KB |
subtask1_09.txt |
AC |
124 ms |
50016 KB |
subtask1_10.txt |
AC |
126 ms |
50016 KB |
subtask1_11.txt |
AC |
126 ms |
50024 KB |
subtask1_12.txt |
AC |
126 ms |
50008 KB |
subtask1_13.txt |
AC |
123 ms |
50020 KB |
subtask1_14.txt |
AC |
125 ms |
50008 KB |
subtask1_15.txt |
AC |
125 ms |
50012 KB |
subtask1_16.txt |
AC |
126 ms |
50020 KB |
subtask1_17.txt |
AC |
143 ms |
50148 KB |
subtask1_18.txt |
AC |
145 ms |
50140 KB |
subtask1_19.txt |
AC |
145 ms |
50144 KB |
subtask1_20.txt |
AC |
146 ms |
50144 KB |
subtask1_21.txt |
AC |
129 ms |
50008 KB |
subtask1_22.txt |
AC |
140 ms |
50020 KB |
subtask1_23.txt |
AC |
143 ms |
50016 KB |
subtask1_24.txt |
AC |
153 ms |
50144 KB |
subtask1_25.txt |
AC |
142 ms |
50016 KB |
subtask1_26.txt |
AC |
145 ms |
50144 KB |
subtask1_27.txt |
AC |
163 ms |
50148 KB |
subtask1_28.txt |
AC |
134 ms |
50016 KB |
subtask1_29.txt |
AC |
133 ms |
50016 KB |
subtask1_30.txt |
AC |
128 ms |
50144 KB |
subtask1_31.txt |
AC |
154 ms |
50140 KB |
subtask1_32.txt |
AC |
154 ms |
50144 KB |
subtask1_33.txt |
AC |
126 ms |
50036 KB |
subtask1_34.txt |
AC |
158 ms |
50140 KB |
subtask1_35.txt |
AC |
126 ms |
50008 KB |
subtask1_36.txt |
AC |
148 ms |
50144 KB |
subtask1_37.txt |
AC |
123 ms |
50008 KB |
subtask1_38.txt |
AC |
121 ms |
49952 KB |
subtask1_39.txt |
AC |
122 ms |
50020 KB |
subtask1_40.txt |
AC |
121 ms |
50020 KB |
subtask1_41.txt |
AC |
121 ms |
50020 KB |
subtask1_42.txt |
AC |
123 ms |
50016 KB |
subtask2_01.txt |
AC |
1515 ms |
53516 KB |
subtask2_02.txt |
AC |
1521 ms |
53388 KB |
subtask2_03.txt |
AC |
1526 ms |
53400 KB |
subtask2_04.txt |
AC |
1528 ms |
53524 KB |
subtask2_05.txt |
AC |
1495 ms |
53400 KB |
subtask2_06.txt |
AC |
1167 ms |
52760 KB |
subtask2_07.txt |
AC |
858 ms |
52508 KB |
subtask2_08.txt |
AC |
549 ms |
51236 KB |
subtask2_09.txt |
AC |
278 ms |
53400 KB |
subtask2_10.txt |
AC |
490 ms |
53396 KB |
subtask2_11.txt |
AC |
734 ms |
53512 KB |
subtask2_12.txt |
AC |
951 ms |
53392 KB |
subtask2_13.txt |
AC |
1306 ms |
53516 KB |
subtask2_14.txt |
AC |
257 ms |
50652 KB |
subtask2_15.txt |
AC |
267 ms |
50528 KB |
subtask2_16.txt |
AC |
277 ms |
50524 KB |
subtask2_17.txt |
AC |
299 ms |
50528 KB |
subtask2_18.txt |
AC |
532 ms |
50964 KB |
subtask2_19.txt |
AC |
185 ms |
50652 KB |
subtask2_20.txt |
AC |
209 ms |
50524 KB |
subtask2_21.txt |
AC |
222 ms |
50524 KB |
subtask2_22.txt |
AC |
231 ms |
50528 KB |
subtask2_23.txt |
AC |
440 ms |
50912 KB |
subtask2_24.txt |
AC |
1318 ms |
53520 KB |
subtask2_25.txt |
AC |
1327 ms |
53524 KB |
subtask2_26.txt |
AC |
1336 ms |
53520 KB |
subtask2_27.txt |
AC |
1365 ms |
53392 KB |
subtask2_28.txt |
AC |
1463 ms |
53524 KB |
subtask2_29.txt |
AC |
242 ms |
50528 KB |
subtask2_30.txt |
AC |
263 ms |
50656 KB |
subtask2_31.txt |
AC |
293 ms |
50656 KB |
subtask2_32.txt |
AC |
1410 ms |
53528 KB |
subtask2_33.txt |
AC |
1416 ms |
53532 KB |
subtask2_34.txt |
AC |
278 ms |
50528 KB |
subtask2_35.txt |
AC |
625 ms |
53520 KB |
subtask2_36.txt |
AC |
842 ms |
53524 KB |
subtask2_37.txt |
AC |
1263 ms |
53512 KB |
subtask2_38.txt |
AC |
1906 ms |
55432 KB |
subtask2_39.txt |
AC |
267 ms |
50660 KB |
subtask2_40.txt |
AC |
193 ms |
50660 KB |
subtask2_41.txt |
AC |
393 ms |
55444 KB |
subtask2_42.txt |
AC |
1973 ms |
55444 KB |
subtask2_43.txt |
AC |
1908 ms |
55448 KB |
subtask2_44.txt |
AC |
271 ms |
50656 KB |
subtask2_45.txt |
AC |
2239 ms |
55444 KB |
subtask2_46.txt |
AC |
215 ms |
50652 KB |
subtask2_47.txt |
AC |
1504 ms |
55440 KB |
subtask2_48.txt |
AC |
132 ms |
50024 KB |
subtask2_49.txt |
AC |
131 ms |
50020 KB |
subtask2_50.txt |
AC |
130 ms |
50016 KB |