Submission #1203396


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){
	dat[k].val+=dat[k].lazy;
	//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].lazy=0;
}

void lazy_update(int k){
	dat[k].val=min(dat[k*2+1].val,dat[k*2+2].val);
}

void 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;
	if(a<=l && r<=b){
		dat[k].lazy+=v;
		lazy_evaluate(k);
		return;
	}
	change(a,b,v,k*2+2,(l+r)/2,r);
	change(a,b,v,k*2+1,l,(l+r)/2);
	lazy_update(k);
	return;
}

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);
	lazy_update(k);
	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]);
		}else{
			scanf("%lld",&order[i][1]);
			day.push_back(order[i][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
Task D - 工場
User ryoissy
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2703 Byte
Status WA
Exec Time 325 ms
Memory 10228 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:84: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:82: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:84: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:86: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:87: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 0 / 600 0 / 400
Status
AC × 3
AC × 15
WA × 5
AC × 30
WA × 20
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 WA 293 ms 8180 KB
in10.txt AC 153 ms 7796 KB
in11.txt WA 312 ms 10100 KB
in12.txt WA 293 ms 10228 KB
in13.txt WA 325 ms 10100 KB
in14.txt WA 312 ms 10228 KB
in15.txt WA 308 ms 9972 KB
in16.txt WA 182 ms 4084 KB
in17.txt WA 184 ms 4212 KB
in18.txt WA 181 ms 4212 KB
in19.txt WA 177 ms 4212 KB
in2.txt WA 282 ms 8180 KB
in20.txt WA 180 ms 4212 KB
in21.txt AC 153 ms 7540 KB
in22.txt AC 158 ms 7540 KB
in23.txt AC 89 ms 4340 KB
in24.txt AC 90 ms 4340 KB
in25.txt AC 98 ms 4340 KB
in3.txt WA 281 ms 8180 KB
in4.txt WA 279 ms 8180 KB
in5.txt WA 282 ms 8180 KB
in6.txt AC 157 ms 7796 KB
in7.txt AC 155 ms 7796 KB
in8.txt AC 154 ms 7796 KB
in9.txt AC 157 ms 7796 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 144 ms 7156 KB
subin10.txt WA 303 ms 9588 KB
subin11.txt WA 235 ms 9844 KB
subin12.txt AC 143 ms 7156 KB
subin13.txt AC 143 ms 7156 KB
subin14.txt AC 143 ms 7156 KB
subin15.txt AC 146 ms 7156 KB
subin16.txt WA 186 ms 4596 KB
subin17.txt AC 89 ms 4340 KB
subin18.txt AC 90 ms 4340 KB
subin19.txt AC 91 ms 4340 KB
subin2.txt AC 145 ms 7156 KB
subin3.txt AC 143 ms 7156 KB
subin4.txt AC 147 ms 7156 KB
subin5.txt AC 146 ms 7156 KB
subin6.txt AC 142 ms 7156 KB
subin7.txt AC 145 ms 7156 KB
subin8.txt WA 292 ms 9588 KB
subin9.txt WA 145 ms 9204 KB