Submission #1203425
Source Code Expand
#include <list>
#include <utility>
#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
#include <cstring>
#include <set>
#include <string>
using namespace std;
#define INF 1000000007LL
typedef long long ll;
int q;
ll k;
int n;
vector<ll> day;
ll order[100005][3];
struct data{
ll val,lazy;
data(){}
data(ll vv,ll rr,ll la){
val=vv;
lazy=la;
}
};
data dat[1<<21];
void lazy_evaluate(int k){
//printf("eval %d %lld\n",k,dat[k].val);
if(k+1<n){
dat[k*2+2].lazy+=dat[k].lazy;
dat[k*2+1].lazy+=dat[k].lazy;
dat[k*2+2].val+=dat[k].lazy;
dat[k*2+1].val+=dat[k].lazy;
}
dat[k].lazy=0;
}
ll change(int a,int b,ll v,int k=0,int l=0,int r=n){
lazy_evaluate(k);
//printf("node a%d b%d l%d r%d k%d v%lld %lld %lld %lld\n",a,b,l,r,k,v,dat[k].val,dat[k].lazy,dat[k].rest);
if(b<=l || r<=a)return dat[k].val;
if(a<=l && r<=b){
dat[k].lazy+=v;
dat[k].val+=v;
lazy_evaluate(k);
return dat[k].val;
}
ll vl=change(a,b,v,k*2+2,(l+r)/2,r);
ll vr=change(a,b,v,k*2+1,l,(l+r)/2);
return (dat[k].val=min(vl,vr));
}
ll query(int a,int b,int k=0,int l=0,int r=n){
lazy_evaluate(k);
//printf("node %d %d %d %lld %lld %lld\n",l,r,k,dat[k].val,dat[k].lazy,dat[k].rest);
if(b<=l || r<=a)return INF*INF;
if(a<=l && r<=b)return dat[k].val;
ll vl=query(a,b,k*2+1,l,(l+r)/2);
ll vr=query(a,b,k*2+2,(l+r)/2,r);
return min(vl,vr);
}
int find(int k=0,int l=0,int r=n){
lazy_evaluate(k);
if(l+1==r)return l;
ll vl=dat[k*2+1].val;
if(vl<0)return find(k*2+1,l,(l+r)/2);
else return find(k*2+2,(l+r)/2,r);
}
int main(void){
scanf("%d%lld",&q,&k);
for(int i=0;i<q;i++){
scanf("%d",&order[i][0]);
if(order[i][0]==1){
scanf("%lld",&order[i][1]);
scanf("%lld",&order[i][2]);
day.push_back(order[i][1]);
day.push_back(order[i][1]+1);
}else{
scanf("%lld",&order[i][1]);
day.push_back(order[i][1]);
day.push_back(order[i][1]+1);
}
}
day.push_back(0);
sort(day.begin(),day.end());
day.erase(unique(day.begin(),day.end()),day.end());
n=1;
while(n<(day.size()+1)){
n*=2;
}
for(int i=0;i<q;i++){
order[i][1]=lower_bound(day.begin(),day.end(),order[i][1])-day.begin();
}
for(int i=0;i<day.size();i++){
ll plu=(ll)(day[i]-day[0])*k;
change(i,i+1,plu);
}
for(int i=0;i<q;i++){
if(order[i][0]==1){
ll va=query(order[i][1],order[i][1]+1);
va=min(va,order[i][2]);
change(order[i][1],day.size(),-va);
while(query(0,n)<0){
int pos=find();
ll vb=query(pos,pos+1);
change(pos,n,-vb);
}
}else{
ll da=day[order[i][1]];
printf("%lld\n",da*k-query(order[i][1],order[i][1]+1));
}
}
return 0;
}
Submission Info
Submission Time
2017-04-05 17:32:53+0900
Task
D - 工場
User
ryoissy
Language
C++14 (GCC 5.4.1)
Score
1000
Code Size
2766 Byte
Status
AC
Exec Time
250 ms
Memory
12656 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:80:26: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘ll* {aka long long int*}’ [-Wformat=]
scanf("%d",&order[i][0]);
^
./Main.cpp:78:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%lld",&q,&k);
^
./Main.cpp:80:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&order[i][0]);
^
./Main.cpp:82:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&order[i][1]);
^
./Main.cpp:83:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&order[i][2]);
...
Judge Result
Set Name
Sample
subtask
All
Score / Max Score
0 / 0
600 / 600
400 / 400
Status
Set Name
Test Cases
Sample
sample1.txt, sample2.txt, sample3.txt
subtask
sample2.txt, subin1.txt, subin10.txt, subin11.txt, subin12.txt, subin13.txt, subin14.txt, subin15.txt, subin16.txt, subin17.txt, subin18.txt, subin19.txt, subin2.txt, subin3.txt, subin4.txt, subin5.txt, subin6.txt, subin7.txt, subin8.txt, subin9.txt
All
sample1.txt, sample2.txt, sample3.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in3.txt, in4.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt, subin1.txt, subin10.txt, subin11.txt, subin12.txt, subin13.txt, subin14.txt, subin15.txt, subin16.txt, subin17.txt, subin18.txt, subin19.txt, subin2.txt, subin3.txt, subin4.txt, subin5.txt, subin6.txt, subin7.txt, subin8.txt, subin9.txt
Case Name
Status
Exec Time
Memory
in1.txt
AC
180 ms
8176 KB
in10.txt
AC
199 ms
12656 KB
in11.txt
AC
245 ms
12656 KB
in12.txt
AC
246 ms
12656 KB
in13.txt
AC
246 ms
12656 KB
in14.txt
AC
250 ms
12656 KB
in15.txt
AC
241 ms
12656 KB
in16.txt
AC
83 ms
4976 KB
in17.txt
AC
83 ms
4976 KB
in18.txt
AC
82 ms
4976 KB
in19.txt
AC
82 ms
4976 KB
in2.txt
AC
181 ms
8176 KB
in20.txt
AC
83 ms
4976 KB
in21.txt
AC
195 ms
12400 KB
in22.txt
AC
196 ms
12400 KB
in23.txt
AC
93 ms
5104 KB
in24.txt
AC
94 ms
5104 KB
in25.txt
AC
93 ms
5104 KB
in3.txt
AC
179 ms
8176 KB
in4.txt
AC
180 ms
8176 KB
in5.txt
AC
177 ms
8176 KB
in6.txt
AC
196 ms
12656 KB
in7.txt
AC
194 ms
12656 KB
in8.txt
AC
195 ms
12656 KB
in9.txt
AC
196 ms
12656 KB
sample1.txt
AC
2 ms
2304 KB
sample2.txt
AC
2 ms
2304 KB
sample3.txt
AC
2 ms
2304 KB
subin1.txt
AC
169 ms
12016 KB
subin10.txt
AC
232 ms
12016 KB
subin11.txt
AC
183 ms
12016 KB
subin12.txt
AC
178 ms
12016 KB
subin13.txt
AC
175 ms
12016 KB
subin14.txt
AC
171 ms
12016 KB
subin15.txt
AC
176 ms
12016 KB
subin16.txt
AC
104 ms
5104 KB
subin17.txt
AC
92 ms
5104 KB
subin18.txt
AC
94 ms
5104 KB
subin19.txt
AC
93 ms
5104 KB
subin2.txt
AC
176 ms
12016 KB
subin3.txt
AC
176 ms
12016 KB
subin4.txt
AC
175 ms
12016 KB
subin5.txt
AC
184 ms
12016 KB
subin6.txt
AC
178 ms
12016 KB
subin7.txt
AC
168 ms
12016 KB
subin8.txt
AC
228 ms
12016 KB
subin9.txt
AC
176 ms
12016 KB