QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #233196 | #7563. Fun on Tree | salvator_noster | WA | 1869ms | 117196kb | C++20 | 9.1kb | 2023-10-31 15:00:12 | 2023-10-31 15:00:13 |
Judging History
answer
#include <bits/stdc++.h>
template <class T>
inline int qlog(T a) {
double x = a;
return ((*(long long*) & x) >> 52 & 2047) - 1023;
}
#define fopen LilyWhite
void fopen(const char *s) {
static char filename[32];
sprintf(filename, "%s.in", s);
freopen(filename, "r", stdin);
sprintf(filename, "%s.out", s);
freopen(filename, "w", stdout);
}
typedef unsigned int u32;
typedef long long ll;
typedef unsigned long long u64;
#define Please return
#define AC 0
#define cin Mizuhashi
#define cout Parsee
#define endl '\n'
class Reader{
private:
static const int BUF_SIZE = 1 << 22;
char BUF_R[BUF_SIZE], *csy1, *csy2;
#ifndef _LOCAL_RUNNING
#define GC (csy1 == csy2 && (csy2 = (csy1 = BUF_R) + fread(BUF_R, 1, BUF_SIZE, stdin), csy1 == csy2) ? EOF : *csy1 ++)
#else
char cur;
#define GC (cur = getchar())
#endif
#define IL inline
public:
IL bool eof() {
#ifndef _LOCAL_RUNNING
return csy1 == csy2 && (csy2 = (csy1 = BUF_R) + fread(BUF_R, 1, BUF_SIZE, stdin), csy1 == csy2);
#else
return cur == EOF;
#endif
}
template <class Ty>
IL Reader& operator >> (Ty &t) {
int u = 0;
char c = GC;
for (t = 0; c < 48 || c > 57; c = GC)
if (c == EOF) break;
else if (c == '-') u = 1;
for ( ; c > 47 && c < 58; c = GC) t = t * 10 + (c ^ 48);
t = u ? -t : t; return *this;
}
IL Reader& operator >> (double &t) {
int tmp, u = 0; char c = GC;
for (tmp = 0; c < 48 || c > 57; c = GC)
if (c == EOF) break;
else if (c == '-') u = 1;
for ( ; c > 47 && c < 58; c = GC) tmp = tmp * 10 + (c ^ 48);
t = (tmp = u ? -tmp : tmp);
if (c == '.') {
double x = 1;
for (c = GC; c > 47 && c < 58; c = GC) t += (x /= 10) * (c ^ 48);
}
return *this;
}
IL Reader& operator >> (char *s) {
char c = GC;
for (*s = 0; c < 33; c = GC) if (c == EOF) return *this;
for ( ; c > 32; c = GC) *s ++ = c;
*s = 0; return *this;
}
IL Reader& operator >> (char &c) {
for (c = GC; c < 33; c = GC) if (c == EOF) return *this;
return *this;
}
}cin;
class Writer{
private:
static const int BUF_SIZE = 1 << 22;
char BUF_W[BUF_SIZE], *csy;
#define IL inline
inline void WC(const char c) {
if (csy - BUF_W == BUF_SIZE) fwrite(BUF_W, 1, BUF_SIZE, stdout), csy = BUF_W;
*csy ++ = c;
}
public:
Writer() : csy(BUF_W) {}
~ Writer() {fwrite(BUF_W, 1, csy - BUF_W, stdout);}
IL void flush() {fwrite(BUF_W, 1, csy - BUF_W, stdout); csy = BUF_W;}
template <class Ty>
IL Writer& operator << (Ty x) {
static int sta[32], top;
if (x < 0) {
WC('-');
do sta[top ++] = - (x % 10); while (x /= 10);
}else do sta[top ++] = x % 10; while (x /= 10);
while (top) WC(sta[-- top] ^ 48);
return *this;
}
IL Writer& operator << (const char &c) {WC(c); return *this;}
IL Writer& operator << (const char *s) {while (*s) WC(*s ++); return *this;}
}cout;
using namespace std;
typedef long long ll;
typedef pair <ll, int> pli;
const int MAX_N = 200000 + 5;
const int MAX_M = 1 << 19;
const ll INF64 = 1e18;
int N, Q, a[MAX_N], w[MAX_N], fa[MAX_N], son[MAX_N], bro[MAX_N];
int sz[MAX_N], bs[MAX_N], dep[MAX_N], tp[MAX_N], dfsn[MAX_N], idfsn[MAX_N], Tm;
ll sum[MAX_N];
struct SegmentNode{
ll lazy;
pli maxv1, maxv2;
}node[MAX_M];
struct Heap{
priority_queue <pli> in, out;
void push(pli x) {in.push(x);}
void erase(pli x) {out.push(x);}
pli top() {
while (!out.empty() && in.top() == out.top()) in.pop(), out.pop();
return in.top();
}
}pq[MAX_N];
inline pli operator + (const pli &a, const ll &b) {return {a.first + b, a.second};}
inline pli& operator += (pli &a, const ll &b) {a.first += b; return a;}
void segment_build1(int i, int l, int r) {
if (l == r) {
node[i].maxv1 = {sum[idfsn[l]] - a[idfsn[l]], -idfsn[l]};
return ;
}
int mid = l + r >> 1;
segment_build1(i << 1, l, mid);
segment_build1(i << 1 | 1, mid + 1, r);
node[i].maxv1 = max(node[i << 1].maxv1, node[i << 1 | 1].maxv1);
}
void segment_build2(int i, int l, int r) {
if (l == r) {
node[i].maxv2 = pq[idfsn[l]].top();
return ;
}
int mid = l + r >> 1;
segment_build2(i << 1, l, mid);
segment_build2(i << 1 | 1, mid + 1, r);
node[i].maxv2 = max(node[i << 1].maxv2, node[i << 1 | 1].maxv2);
}
void segment_modify(int i, int l, int r, int ql, int qr, ll v) {
if (l < ql || r > qr) {
int mid = l + r >> 1;
if (ql <= mid) segment_modify(i << 1, l, mid, ql, qr, v);
if (mid < qr) segment_modify(i << 1 | 1, mid + 1, r, ql, qr, v);
node[i].maxv1 = max(node[i << 1].maxv1, node[i << 1 | 1].maxv1) + node[i].lazy;
node[i].maxv2 = max(node[i << 1].maxv2, node[i << 1 | 1].maxv2) + node[i].lazy;
}else {
node[i].lazy += v;
node[i].maxv1 += v;
node[i].maxv2 += v;
}
}
void segment_modify(int i, int l, int r, int x, pli v) {
if (l == r) {
node[i].maxv2 = v;
return ;
}
int mid = l + r >> 1;
mid < x ? segment_modify(i << 1 | 1, mid + 1, r, x, v + (-node[i].lazy)) : segment_modify(i << 1, l, mid, x, v + (-node[i].lazy));
node[i].maxv2 = max(node[i << 1].maxv2, node[i << 1 | 1].maxv2) + node[i].lazy;
}
ll segment_query(int x, int i = 1, int l = 1, int r = N) {
ll res = 0;
while (l < r) {
res += node[i].lazy;
int mid = l + r >> 1;
if (mid < x) {
l = mid + 1;
i = i << 1 | 1;
}else {
r = mid;
i <<= 1;
}
}
return res + node[i].lazy;
}
pli segment_query1(int i, int l, int r, int ql, int qr) {
if (l < ql || r > qr) {
pli res = {-INF64, -INF64};
int mid = l + r >> 1;
if (ql <= mid) res = segment_query1(i << 1, l, mid, ql, qr);
if (mid < qr) res = max(res, segment_query1(i << 1 | 1, mid + 1, r, ql, qr));
return res + node[i].lazy;
}else {
return node[i].maxv1;
}
}
pli segment_query2(int i, int l, int r, int ql, int qr) {
if (l < ql || r > qr) {
pli res = {-INF64, -INF64};
int mid = l + r >> 1;
if (ql <= mid) res = segment_query2(i << 1, l, mid, ql, qr);
if (mid < qr) res = max(res, segment_query2(i << 1 | 1, mid + 1, r, ql, qr));
return res + node[i].lazy;
}else {
return node[i].maxv2;
}
}
void dfs1(int u) {
sz[u] = 1;
dep[u] = dep[fa[u]] + 1;
sum[u] = sum[fa[u]] + w[u];
for (int v = son[u]; v; v = bro[v]) {
dfs1(v);
sz[u] += sz[v];
if (sz[bs[u]] < sz[v]) bs[u] = v;
}
}
void dfs2(int u, int gr) {
tp[u] = gr;
dfsn[u] = ++ Tm;
idfsn[Tm] = u;
if (bs[u]) dfs2(bs[u], gr);
for (int v = son[u]; v; v = bro[v])
if (v != bs[u]) dfs2(v, v);
}
void dfs3(int u) {
pq[u].push({-sum[u] - a[u], -u});
for (int v = son[u]; v; v = bro[v]) {
dfs3(v);
if (v != bs[u]) {
pq[u].push(segment_query1(1, 1, N, dfsn[v], dfsn[v] + sz[v] - 1) + (-sum[u] * 2));
}
}
}
void modify(int u, int val) {
int v = u;
while (tp[u] != 1) {
u = tp[u];
pq[fa[u]].erase(segment_query1(1, 1, N, dfsn[u], dfsn[u] + sz[u] - 1) + (-sum[fa[u]] * 2));
u = fa[u];
}
u = v;
segment_modify(1, 1, N, dfsn[u], dfsn[u] + sz[u] - 1, -val);
while (tp[u] != 1) {
u = tp[u];
pq[fa[u]].push(segment_query1(1, 1, N, dfsn[u], dfsn[u] + sz[u] - 1) + (-sum[fa[u]] * 2));
u = fa[u];
segment_modify(1, 1, N, dfsn[u], pq[u].top());
}
}
pli query(int u) {
pli res = {-INF64, -INF64};
ll s = sum[u];
int v = 0;
while (u) {
if (bs[u]) res = max(res, segment_query1(1, 1, N, dfsn[bs[u]], dfsn[bs[u]] + sz[bs[u]] - 1) + (-sum[u] * 2));
if (v) {
pq[u].erase(segment_query1(1, 1, N, dfsn[v], dfsn[v] + sz[v] - 1) + (-sum[u] * 2));
segment_modify(1, 1, N, dfsn[u], pq[u].top());
}
res = max(res, segment_query2(1, 1, N, dfsn[tp[u]], dfsn[u]));
if (v) {
pq[u].push(segment_query1(1, 1, N, dfsn[v], dfsn[v] + sz[v] - 1) + (-sum[u] * 2));
segment_modify(1, 1, N, dfsn[u], pq[u].top());
}
v = tp[u]; u = fa[v];
}
return res + s;
}
int main() {
cin >> N >> Q;
for (int i = 1; i <= N; i ++) cin >> a[i];
for (int i = 2; i <= N; i ++) {
cin >> fa[i] >> w[i];
bro[i] = son[fa[i]];
son[fa[i]] = i;
}
dfs1(1); dfs2(1, 1);
segment_build1(1, 1, N);
dfs3(1);
segment_build2(1, 1, N);
while (Q --) {
int x, y, v;
cin >> x >> y >> v;
modify(y, v);
pli res = query(x);
cout << -res.second << ' ' << res.first << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 45020kb
input:
6 6 1 1 4 5 1 4 1 5 2 0 3 2 4 1 5 6 3 2 -100000 1 2 100000 1 1 0 2 2 66 3 1 5 4 4 -3
output:
6 100005 6 10 6 10 1 4 1 -1 1 1
result:
ok 6 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 44692kb
input:
5 6 -10 0 2 -4 8 1 7 1 1 2 2 2 -2 1 1 100 2 1 -100 1 1 0 4 3 10 2 5 3 5 2 2
output:
4 -87 1 17 4 13 1 19 1 17 1 15
result:
ok 6 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 45076kb
input:
6 3 0 0 0 0 0 0 1 10 1 10 1 -100 4 10 4 11 1 1 0 4 1 0 1 4 1000
output:
2 10 6 11 2 10
result:
ok 3 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 44608kb
input:
2 0 1 1 1 3
output:
result:
ok 0 lines
Test #5:
score: -100
Wrong Answer
time: 1869ms
memory: 117196kb
input:
200000 200000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 ...
output:
119017 15000000000 120167 17000000000 119017 15000000000 119017 15000000000 120167 17000000000 120167 15000000000 120167 16000000000 119017 17000000000 119017 16000000000 119017 12000000000 119017 17000000000 120167 16000000000 120167 14000000000 120167 17000000000 120167 18000000000 120167 16000000...
result:
wrong answer 68276th lines differ - expected: '130674 14000000000', found: '191485 15000000000'