Submission #1203393

---

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]);
			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],n,-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

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