Submission #548262

#	Time	Username	Problem	Language	Result	Execution time	Memory
548262		duality	Ants and Sugar (JOI22_sugar)	C++17	0 / 100	1333 ms	71120 KiB

sugar

#define DEBUG 0

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

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------

int T[500000],X[500000],A[500000];
vpii all;
struct node { LLI ans,ss,ee,both,sum; };
node com(node a,node b) {
    node c;
    c.ans = max(max(a.ans+b.ans,a.ss+b.ee),(LLI) -3e18);
    c.ss = max(max(max(a.ans+b.ss,a.ss+b.both),a.ss+b.sum),(LLI) -3e18);
    c.ee = max(max(max(a.ee+b.ans,a.both+b.ee),a.sum+b.ee),(LLI) -3e18);
    c.both = max(max(a.ee+b.ss,a.both+b.both),(LLI) -3e18);
    c.sum = a.sum+b.sum;
    return c;
}
int on[1500000];
node tree[1 << 22];
LLI lazys[1 << 22],lazye[1 << 22];
int build(int s,int e,int i) {
    if (s == e) {
        tree[i] = (node){0LL,(LLI) -3e18,(LLI) -3e18,(LLI) -3e18,0LL};
        return 0;
    }

    int mid = (s+e) / 2;
    build(s,mid,2*i+1),build(mid+1,e,2*i+2);
    tree[i] = (node){0LL,(LLI) -3e18,(LLI) -3e18,(LLI) -3e18,0LL};
    return 0;
}
int prop(int s,int e,int i) {
    if (lazys[i] != 0) {
        tree[i].ss += lazys[i],tree[i].both += lazys[i];
        if (s != e) lazys[2*i+1] += lazys[i],lazys[2*i+2] += lazys[i];
        lazys[i] = 0;
    }
    if (lazye[i] != 0) {
        tree[i].ee += lazye[i],tree[i].both += lazye[i];
        if (s != e) lazye[2*i+1] += lazye[i],lazye[2*i+2] += lazye[i];
        lazye[i] = 0;
    }
    return 0;
}
int update(int s,int e,int ai,int i,int num) {
    prop(s,e,i);
    if ((s > ai) || (e < ai)) return 0;
    else if (s == e) {
        tree[i].sum += num;
        return 0;
    }

    int mid = (s+e) / 2;
    update(s,mid,ai,2*i+1,num),update(mid+1,e,ai,2*i+2,num);
    tree[i] = com(tree[2*i+1],tree[2*i+2]);
    return 0;
}
int activate(int s,int e,int ai,int i) {
    prop(s,e,i);
    if ((s > ai) || (e < ai)) return 0;
    else if (s == e) {
        if (all[s].second == -1) tree[i].ss += 3e18;
        else tree[i].ee += 3e18;
        return 0;
    }

    int mid = (s+e) / 2;
    activate(s,mid,ai,2*i+1),activate(mid+1,e,ai,2*i+2);
    tree[i] = com(tree[2*i+1],tree[2*i+2]);
    return 0;
}
int update2(int s,int e,int as,int ae,int i,int t,int num) {
    prop(s,e,i);
    if ((s > ae) || (e < as)) return 0;
    else if ((s >= as) && (e <= ae) && (s == e)) {
        if (t == 0) lazys[i] += num;
        else lazye[i] += num;
        prop(s,e,i);
        return 0;
    }

    int mid = (s+e) / 2;
    update2(s,mid,as,ae,2*i+1,t,num),update2(mid+1,e,as,ae,2*i+2,t,num);
    tree[i] = com(tree[2*i+1],tree[2*i+2]);
    return 0;
}
int main() {
    int i;
    int Q,L;
    scanf("%d %d",&Q,&L);
    for (i = 0; i < Q; i++) {
        scanf("%d %d %d",&T[i],&X[i],&A[i]);
        if (T[i] == 1) all.pb(mp(X[i]-L,-1)),all.pb(mp(X[i],0)),all.pb(mp(X[i]+L,1));
        else all.pb(mp(X[i],0));
    }

    LLI sum = 0;
    sort(all.begin(),all.end());
    all.resize(unique(all.begin(),all.end())-all.begin());
    build(0,all.size()-1,0);
    for (i = 0; i < Q; i++) {
        if (T[i] == 1) {
            int p = lower_bound(all.begin(),all.end(),mp(X[i]-L,-1))-all.begin();
            int q = lower_bound(all.begin(),all.end(),mp(X[i],0))-all.begin();
            int r = lower_bound(all.begin(),all.end(),mp(X[i]+L,1))-all.begin();
            if (!on[p]) activate(0,all.size()-1,p,0),on[p] = 1;
            if (!on[r]) activate(0,all.size()-1,r,0),on[r] = 1;
            update(0,all.size()-1,q,0,A[i]);
            update2(0,all.size()-1,p+1,q,0,0,-A[i]);
            update2(0,all.size()-1,q,r-1,0,1,-A[i]);
            sum += A[i];
        }
        else {
            int p = lower_bound(all.begin(),all.end(),mp(X[i],0))-all.begin();
            update(0,all.size()-1,p,0,-A[i]);
        }
        printf("%lld\n",sum-tree[0].ans);
    }

    return 0;
}

Compilation message (stderr)

sugar.cpp: In function 'int main()':
sugar.cpp:142:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |     scanf("%d %d",&Q,&L);
      |     ~~~~~^~~~~~~~~~~~~~~
sugar.cpp:144:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |         scanf("%d %d %d",&T[i],&X[i],&A[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 16
• Subtask 3: 0 / 26
• Subtask 4: 0 / 52