Submission #144236

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
144236	2019-08-16 10:58:43	osaaateiasavtnl	Cake 3 (JOI19_cake3)	C++14	100 / 100	1460 ms	206304 KiB

cake3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
const int N = 2e5 + 7, INF = 1e18 + 7;
int n, m;
struct El { int v, c; } a[N];
struct Node { int cnt, sum; Node *l, *r; Node () { cnt = sum = 0; l = r = NULL; } };
vector <int> c;
Node *build(int tl, int tr) {
    Node *ans = new Node();
    if (tl == tr) return ans;
    int tm = (tl + tr) >> 1;
    ans->l = build(tl, tm); ans->r = build(tm + 1, tr);
    return ans;
}
void relax(Node *t) { t->cnt = t->l->cnt + t->r->cnt; t->sum = t->l->sum + t->r->sum; }
Node *add(Node *t, int tl, int tr, int p) {
    Node *ans = new Node();
    if (tl == tr) { ans->cnt = t->cnt + 1; ans->sum = t->sum + c[p]; return ans; }
    int tm = (tl + tr) >> 1;
    if (p <= tm) { ans->l = add(t->l, tl, tm, p); ans->r = t->r; }
    else { ans->l = t->l; ans->r = add(t->r, tm + 1, tr, p); }
    relax(ans); return ans;
}
int get(Node *l, Node *r, int tl, int tr, int k) {
    if (tl == tr) return c[tl] * k;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 76 / 76