Submission #553749

#	Time	Username	Problem	Language	Result	Execution time	Memory
553749		QwertyPi	사탕 분배 (IOI21_candies)	C++17	100 / 100	347 ms	39352 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int N = 2e5+5;
const ll inf = 1LL << 60;
vector<int> L, R, V;
int q;

int bound(int l, int r, int x){
	if(x < l) return l;
	if(x > r) return r;
	return x;
}
namespace Segtree{
	struct node{
		ll mxp = 0, mnp = 0, s = 0;
		node(){}
		node(ll v) : mxp(max(v, 0LL)), mnp(min(v, 0LL)), s(v){};
	} t[N * 4];
	
	node merge(node a, node b){
		if(a.mxp == inf || b.mxp == inf) return a.mxp == inf ? b : a;
		node ret;
		ret.mxp = max(a.mxp, a.s + b.mxp);
		ret.mnp = min(a.mnp, a.s + b.mnp);
		ret.s = a.s + b.s;
		return ret;
	}
	
	void build(int v = 0, int l = 0, int r = q - 1){
		if(l == r){
			t[v] = node(0); return;
		}
		int m = (l + r) / 2;
		build(v * 2 + 1, l, m);
		build(v * 2 + 2, m + 1, r);
		t[v] = merge(t[v * 2 + 1], t[v * 2 + 2]);
	}
	void add(int id, int v = 0, int tl = 0, int tr = q - 1){
		if(tl == tr){
			t[v] = node(V[tl]); return;
		}
		int tm = (tl + tr) / 2;
		if(id <= tm){
			add(id, v * 2 + 1, tl, tm);
		}else{
			add(id, v * 2 + 2, tm + 1, tr);
		}
		t[v] = merge(t[v * 2 + 1], t[v * 2 + 2]);
	}
	
	void remove(int id, int v = 0, int tl = 0, int tr = q - 1){
		if(tl == tr){
			t[v] = node(0); return;
		}
		int tm = (tl + tr) / 2;
		if(id <= tm){
			remove(id, v * 2 + 1, tl, tm);
		}else{
			remove(id, v * 2 + 2, tm + 1, tr);
		}
		t[v] = merge(t[v * 2 + 1], t[v * 2 + 2]);
	}
	
	int query(int c){
		int v = 0, tl = 0, tr = q - 1;
		node cur {0};
		while(tl != tr){
			int tm = (tl + tr) / 2;
			node nxt = merge(t[v * 2 + 2], cur);
			if(nxt.mxp - nxt.mnp <= c){
				cur = nxt;
				tr = tm;
				v = v * 2 + 1;
			}else{
				tl = tm + 1;
				v = v * 2 + 2;
			}
		}
		node nxt = merge(t[v], cur);
		if(nxt.mxp - nxt.mnp <= c){
			cur = nxt;
			tr--;
		}
		int st = (tr < 0 ? 0 : bound(0, c, V[tr]));
		return bound(-cur.mnp, c - cur.mxp, st) + cur.s;
	}
};

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size();
    vector<int> ans(n);
    q = l.size();
    ::L = l, ::R = r, ::V = v;
    vector<pii> Q;
    for(int i = 0; i < q; i++){
    	Q.push_back({l[i], i+1});
    	Q.push_back({r[i]+1, -i-1});
	}
	sort(Q.begin(), Q.end());
	int qi = 0;
	for(int i = 0; i < n; i++){
		while(qi < Q.size() && Q[qi].fi <= i){
			if(Q[qi].se > 0) Segtree::add(Q[qi].se - 1);
			else Segtree::remove(-Q[qi].se - 1);
			qi++;
		}
		ans[i] = Segtree::query(c[i]);
	}
    return ans;
}

Compilation message (stderr)

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:107:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |   while(qi < Q.size() && Q[qi].fi <= i){
      |         ~~~^~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33