Problem

WA 50PTS

#include <bits/stdc++.h>
#define int long long
using namespace std;

typedef long long LL;

const int N = 2e6 + 5;
int P[N], D[N], a[N], sum[N], P1[N], D1[N];
int m, p;
struct Node
{
    int l, r;
    int v;  
}tr[N * 2];

void pushup(int u)  
{
    tr[u].v = min(tr[u << 1].v, tr[u << 1 | 1].v);
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, INT_MAX};
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;

    int mid = tr[u].l + tr[u].r >> 1;
    int v = INT_MAX;
    if (l <= mid) v = query(u << 1, l, r);
    if (r > mid) v = min(v, query(u << 1 | 1, l, r));

    return v;
}

void modify(int u, int x, int v)
{
    if (tr[u].l == x && tr[u].r == x) tr[u].v = v;
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}
int ans[N];

signed main()
{
    int n; cin >> n;
    for(int i = 1;i <= n;i ++ ) {
        cin >> P[i] >> D[i];
        P1[i] = P[i], D1[i] = D[i];
        a[i] = P[i] - D[i];
    }
    build(1, 1, n * 2);
    int f = 0;
    for(int i = 1;i <= n;i ++ ) {
        sum[i] = sum[i - 1] + a[i];
        if(sum[i] < 0 && !f) {ans[i] = 0; f = 1;}
        modify(1, i, sum[i]);
    }
    if(!f) ans[1] = 1;
    for(int i = 2;i <= n;i ++ ){
        sum[n + i - 1] = sum[n + i - 2] + a[i - 1];
        modify(1, n + i - 1, sum[n + i - 1]);
        if(query(1, i, n + i - 1) < sum[i - 1]) ans[i] = 0;
        else ans[i] = 1;
    }
    memset(a, 0, sizeof(a));
    memset(tr, 0, sizeof(tr));
    build(1, 1, n * 2);
    memset(sum, 0, sizeof(sum));
    D[1] = D1[n];
    for(int i = 2;i <= n;i ++ ) D[i] = D1[n - i + 1], P[i] = P1[n - i + 2];
    // for(int i= 1;i <= n;i ++ ) cout << P[i] << ' ' << D[i] << endl;
    for(int i = 1;i <= n;i ++ ) {
        a[i] = P[i] - D[i];
    }
    f = 0;
    for(int i = 1;i <= n;i ++ ) {
        sum[i] = sum[i - 1] + a[i];
        if(sum[i] < 0 && !f) { f = 1;}
        modify(1, i, sum[i]);
    }
    if(!f) ans[1] = 1;
    for(int i = 2;i <= n;i ++ ){
        sum[n + i - 1] = sum[n + i - 2] + a[i - 1];
        modify(1, n + i - 1, sum[n + i - 1]);
        // cout << query(1, i, n + i - 1) << endl;
        if(query(1, i, n + i - 1) < sum[i - 1]);
        else ans[n - i + 2] = 1;
    }
    for(int i = 1;i <= n;i ++ ) cout << (ans[i] ? "TAK" : "NIE") << endl;
    return 0;
}