Submission #1285503

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285503		kerem	코알라 (JOI13_koala)	C++20	100 / 100	277 ms	134220 KiB

koala

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define pb push_back
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define N 2000
#define inf (int)1e18
typedef pair<int,int> pii;

struct Node{
	int val,lz;
	int l,r;
	Node(){val=-inf;lz=0;l=r=-1;}
};

vector<Node> st;
int cnt=0;

int addNode(){
	st.pb(Node());
	return cnt++;
}
int getVal(int node){
	return node==-1?-inf:st[node].val;
}

void push(int node,bool leaf){
	if(st[node].lz!=0){
		if(!leaf){
			if(st[node].l<0) st[node].l=addNode();
			if(st[node].r<0) st[node].r=addNode();
			st[st[node].l].lz+=st[node].lz;
			st[st[node].r].lz+=st[node].lz;
		}
		st[node].val+=st[node].lz;
		st[node].lz=0;
	}
}
int update(int node,int l,int r,int ql,int qr,int val){
	if(node>=0) push(node,l==r);
	if(r<ql || qr<l) return node;
	if(node<0) node=addNode();
	if(ql<=l && r<=qr){
		st[node].lz+=val;
		push(node,l==r);
		return node;
	}
	int mid=(l+r)/2;
	st[node].l=update(st[node].l,l,mid,ql,qr,val);
	st[node].r=update(st[node].r,mid+1,r,ql,qr,val);
	st[node].val=max(getVal(st[node].l),getVal(st[node].r));
	return node;
}
int update(int node,int l,int r,int qx,int val){
	if(node>=0) push(node,l==r);
	if(r<qx || qx<l) return node;
	if(node<0) node=addNode();
	if(l==r){
		st[node].val=max(st[node].val,val);
		return node;
	}
	int mid=(l+r)/2;
	st[node].l=update(st[node].l,l,mid,qx,val);
	st[node].r=update(st[node].r,mid+1,r,qx,val);
	st[node].val=max(getVal(st[node].l),getVal(st[node].r));
	return node;
}
void print(int node,int l,int r){ 
	if(node<0) return;           
	cout << st[node].val sp st[node].lz sp l sp r << endl;
	int mid=(l+r)/2;
	print(st[node].l,l,mid);
	print(st[node].r,mid+1,r);
}
void solve(){
	addNode();
	int bas,son,d,a,n;
	cin >> bas >> son >> d >> a >> n;
	int t[n+1],c[n+1],dp[n+1];
	t[0]=bas;c[0]=0;
	for(int i=1;i<=n;i++)
		cin >> t[i] >> c[i];
	
	update(0,0,d-1,son%d,0);
	//~ print(0,0,d-1);cout << "-------" << "\n";
	for(int i=n;i>=0;i--){
		int nxt=(i==n?son:t[i+1]);
		update(0,0,d-1,0,d-1,(nxt-t[i]+d-1)/d*-a);
		int l=nxt%d,r=t[i]%d;
		if(l<=r)
			update(0,0,d-1,l+1,r,a);
		else{
			update(0,0,d-1,l+1,d-1,a);
			update(0,0,d-1,0,r,a);
		}
		//~ print(0,0,d-1);cout << "-------" << "\n";
		dp[i]=st[0].val+c[i];
		update(0,0,d-1,t[i]%d,dp[i]);
		//~ cout << i sp dp[i] << endl;
	}
	cout << dp[0] << endl;
}
int32_t main(){
	//~ freopen("hopscotch.in","r",stdin);
	//~ freopen("hopscotch.out","w",stdout);
	
	cout << fixed << setprecision(0);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	int test=1;
	//~ cin >> test;
	while(test--) solve();
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50