| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 437068 | p3rfect | 사탕 분배 (IOI21_candies) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <cstdio>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <ctime>
#include <vector>
#include <set>
#include <iterator>
#include <map>
#include <functional>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <queue>
#include <deque>
#include <time.h>
#include <bitset>
#define ll long long
#define ld long double
#define y1 abc
#define endl '\n'
#define fi first
#define se second
#define m_p make_pair
#define pb push_back
#define pf push_front
#define MAXLL 9000000000000000000LL
#define MAXINT 2000000000
#define MINLL -9000000000000000000LL
#define MININT -2000000000
#define stoi aaaaavasd
#define pll pair < ll, ll >
#define pii pair < int, int >
using namespace std;
using namespace __gnu_pbds;
typedef tree< int, null_type, less< int >, rb_tree_tag, tree_order_statistics_node_update > ordered_set;
const ld pi = acos(-1);
const ll md = 1e9 + 7;
clock_t start_time = clock();
ll n, q, i, j;
vector < int > ans;
vector < pll > tg[200501];
struct segtree
{
struct node
{
ll mn = 0, mx = 0, p = 0;
};
node t[200501];
ll sz = 1, lst = 0;
void build()
{
while (sz < q + 3) sz *= 2;
sz--;
}
void propagate(ll nom, ll l, ll r)
{
if (t[nom].p == 0 || l == r) return;
t[nom * 2].mn += t[nom].p;
t[nom * 2].mx += t[nom].p;
t[nom * 2].p += t[nom].p;
t[nom * 2 + 1].mn += t[nom].p;
t[nom * 2 + 1].mx += t[nom].p;
t[nom * 2 + 1].p += t[nom].p;
t[nom].p = 0;
}
void update(ll nom, ll l, ll r, ll cl, ll cr, ll x)
{
propagate(nom, l, r);
if (l > cr || r < cl) return;
if (l >= cl && r <= cr){
t[nom].p += x;
t[nom].mn += x;
t[nom].mx += x;
return;
}
ll mid = (l + r) / 2;
update(nom * 2, l, mid, cl, cr, x);
update(nom * 2 + 1, mid + 1, r, cl, cr, x);
t[nom].mn = min(t[nom * 2].mn, t[nom * 2 + 1].mn);
t[nom].mx = max(t[nom * 2].mx, t[nom * 2 + 1].mx);
}
void update(ll l, ll r, ll x)
{
lst += x;
update(1, 0, sz, l, r, x);
}
pair < ll, pll > get(ll nom, ll l, ll r, ll c, ll mx, ll mn)
{
propagate(nom, l, r);
if (l == r) return {l, {mn, mx}};
ll mid = (l + r) / 2;
if (max(t[nom * 2 + 1].mx, mx) - min(t[nom * 2 + 1].mn, mn) > c){
return get(nom * 2 + 1, mid + 1, r, c, mx, mn);
}
else{
return get(nom * 2, l, mid, c, max(mx, t[nom * 2 + 1].mx), min(mn, t[nom * 2 + 1].mn));
}
}
ll get(ll c)
{
pair < ll, pll > g = get(1, 0, sz, c, MININT, MAXINT);
ll idx = g.fi, mn = g.se.fi, mx = g.se.se;
idx += sz + 1;
if (t[idx].mn < lst) return c - (mx - lst);
else return lst - mn;
}
};
segtree t;
vector < int > distribute_candies(vector < int > c, vector < int > l, vector < int > r, vector < int > v)
{
n = c.size();
q = l.size();
n--;
q--;
for (i = 0; i <= q; i++){
tg[l[i]].pb({i, v[i]});
tg[r[i] + 1].pb({i, -v[i]});
}
t.build();
t.update(0, q + 2, MAXINT);
t.update(1, q + 2, MININT);
ans.resize(n + 1);
for (i = 0; i <= n; i++){
for (pll x : tg[i]){
t.update(x.fi + 2, q + 2, x.se);
}
ans[i] = t.get(c[i]);
}
return ans;
}
int main()
{
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
ll q = 1;
// cin >> q;
// while (q--){
// solve();
// }
vector < int > v = distribute_candies({10, 15, 13}, {0, 0}, {2, 1}, {20, -11});
for (i = 0; i < 3; i++) cout << v[i] << " ";
cout << endl;
#ifdef LOCAL
cout << endl;
cout << "Time = " << (ld)(clock() - start_time) / CLOCKS_PER_SEC << endl;
#endif
return 0;
}