oj.uz

Submission #548264

# Submission time Handle Problem Language Result Execution time Memory
548264 2022-04-12T20:25:11 Z duality Ants and Sugar (JOI22_sugar) C++17
16 / 100
 2156 ms 141452 KB 
#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(max(a.ee+b.ss,a.both+b.both),max(a.both+b.sum,a.sum+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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1431 ms 70860 KB Output is correct
5 Correct 629 ms 69788 KB Output is correct
6 Correct 1539 ms 126264 KB Output is correct
7 Correct 628 ms 69848 KB Output is correct
8 Correct 1945 ms 138408 KB Output is correct
9 Correct 1437 ms 141452 KB Output is correct
10 Correct 2156 ms 139436 KB Output is correct
11 Correct 1466 ms 138900 KB Output is correct
12 Correct 630 ms 67596 KB Output is correct
13 Correct 938 ms 125600 KB Output is correct
14 Correct 1385 ms 137780 KB Output is correct
15 Correct 1375 ms 137548 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -