oj.uz

Submission #548276

# Submission time Handle Problem Language Result Execution time Memory
548276 2022-04-12T20:50:54 Z duality Ants and Sugar (JOI22_sugar) C++17
48 / 100
 4000 ms 265268 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]);
    //cout<<"tree["<<s<<","<<e<<"]:"<<tree[i].ss<<","<<tree[i].ee<<","<<tree[i].ans<<","<<tree[i].both<<","<<tree[i].sum<<endl;
    //cout<<"tree["<<s<<","<<mid<<"]:"<<tree[2*i+1].ss<<","<<tree[2*i+1].ee<<","<<tree[2*i+1].ans<<","<<tree[2*i+1].both<<","<<tree[2*i+1].sum<<endl;
    //cout<<"tree["<<mid+1<<","<<e<<"]:"<<tree[2*i+2].ss<<","<<tree[2*i+2].ee<<","<<tree[2*i+2].ans<<","<<tree[2*i+2].both<<","<<tree[2*i+2].sum<<endl;
    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) {
        //cout<<"activate tree["<<s<<"]: "<<tree[i].ss<<","<<tree[i].ee<<endl;
        if (all[s].second == -1) tree[i].ss += (LLI) 3e18;
        else tree[i].ee += (LLI) 3e18;
        //cout<<s<<": ss="<<tree[i].ss<<endl;
        //cout<<s<<": ee="<<tree[i].ee<<endl;
        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)) {
        if (t == 0) lazys[i] += num;
        else lazye[i] += num;
        prop(s,e,i);
        //cout<<"tree["<<s<<"]: "<<tree[i].ss<<","<<tree[i].ee<<endl;
        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 (pii p: all) cout<<p.first<<","<<p.second<<" ";
    //cout<<endl;
    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]);
            //cout<<p<<";"<<q<<";"<<r<<endl;
            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:149:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |     scanf("%d %d",&Q,&L);
      |     ~~~~~^~~~~~~~~~~~~~~
sugar.cpp:151:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |         scanf("%d %d %d",&T[i],&X[i],&A[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 6 ms 968 KB Output is correct
7 Correct 4 ms 832 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 7 ms 1364 KB Output is correct
11 Correct 8 ms 1480 KB Output is correct
12 Correct 9 ms 1504 KB Output is correct
13 Correct 9 ms 1520 KB Output is correct
14 Correct 5 ms 724 KB Output is correct
15 Correct 4 ms 852 KB Output is correct
16 Correct 18 ms 2516 KB Output is correct
17 Correct 23 ms 2476 KB Output is correct
18 Correct 12 ms 2388 KB Output is correct
19 Correct 8 ms 1484 KB Output is correct
20 Correct 13 ms 2504 KB Output is correct
21 Correct 14 ms 1480 KB Output is correct
22 Correct 15 ms 2388 KB Output is correct
23 Correct 10 ms 1512 KB Output is correct
24 Correct 14 ms 2388 KB Output is correct
25 Correct 9 ms 1364 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1526 ms 73928 KB Output is correct
5 Correct 689 ms 68556 KB Output is correct
6 Correct 1858 ms 123920 KB Output is correct
7 Correct 774 ms 68516 KB Output is correct
8 Correct 2298 ms 135840 KB Output is correct
9 Correct 1586 ms 137780 KB Output is correct
10 Correct 2232 ms 135932 KB Output is correct
11 Correct 1608 ms 138048 KB Output is correct
12 Correct 756 ms 66952 KB Output is correct
13 Correct 1020 ms 126036 KB Output is correct
14 Correct 1522 ms 135132 KB Output is correct
15 Correct 1623 ms 135096 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 702 ms 67956 KB Output is correct
3 Correct 957 ms 127172 KB Output is correct
4 Correct 1528 ms 135352 KB Output is correct
5 Correct 1528 ms 135416 KB Output is correct
6 Correct 1656 ms 131968 KB Output is correct
7 Correct 98 ms 9060 KB Output is correct
8 Correct 796 ms 67468 KB Output is correct
9 Correct 1233 ms 71840 KB Output is correct
10 Correct 2166 ms 136668 KB Output is correct
11 Correct 2230 ms 136280 KB Output is correct
12 Correct 2170 ms 136064 KB Output is correct
13 Correct 2168 ms 135304 KB Output is correct
14 Correct 2191 ms 135924 KB Output is correct
15 Correct 2049 ms 130944 KB Output is correct
16 Correct 2149 ms 134836 KB Output is correct
17 Correct 2414 ms 137540 KB Output is correct
18 Correct 2553 ms 147204 KB Output is correct
19 Correct 2553 ms 147496 KB Output is correct
20 Correct 2517 ms 146680 KB Output is correct
21 Correct 2599 ms 147456 KB Output is correct
22 Correct 2728 ms 146612 KB Output is correct
23 Correct 2652 ms 146596 KB Output is correct
24 Correct 2603 ms 138868 KB Output is correct
25 Correct 2648 ms 143156 KB Output is correct

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 6 ms 968 KB Output is correct
7 Correct 4 ms 832 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 7 ms 1364 KB Output is correct
11 Correct 8 ms 1480 KB Output is correct
12 Correct 9 ms 1504 KB Output is correct
13 Correct 9 ms 1520 KB Output is correct
14 Correct 5 ms 724 KB Output is correct
15 Correct 4 ms 852 KB Output is correct
16 Correct 18 ms 2516 KB Output is correct
17 Correct 23 ms 2476 KB Output is correct
18 Correct 12 ms 2388 KB Output is correct
19 Correct 8 ms 1484 KB Output is correct
20 Correct 13 ms 2504 KB Output is correct
21 Correct 14 ms 1480 KB Output is correct
22 Correct 15 ms 2388 KB Output is correct
23 Correct 10 ms 1512 KB Output is correct
24 Correct 14 ms 2388 KB Output is correct
25 Correct 9 ms 1364 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1526 ms 73928 KB Output is correct
30 Correct 689 ms 68556 KB Output is correct
31 Correct 1858 ms 123920 KB Output is correct
32 Correct 774 ms 68516 KB Output is correct
33 Correct 2298 ms 135840 KB Output is correct
34 Correct 1586 ms 137780 KB Output is correct
35 Correct 2232 ms 135932 KB Output is correct
36 Correct 1608 ms 138048 KB Output is correct
37 Correct 756 ms 66952 KB Output is correct
38 Correct 1020 ms 126036 KB Output is correct
39 Correct 1522 ms 135132 KB Output is correct
40 Correct 1623 ms 135096 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 702 ms 67956 KB Output is correct
43 Correct 957 ms 127172 KB Output is correct
44 Correct 1528 ms 135352 KB Output is correct
45 Correct 1528 ms 135416 KB Output is correct
46 Correct 1656 ms 131968 KB Output is correct
47 Correct 98 ms 9060 KB Output is correct
48 Correct 796 ms 67468 KB Output is correct
49 Correct 1233 ms 71840 KB Output is correct
50 Correct 2166 ms 136668 KB Output is correct
51 Correct 2230 ms 136280 KB Output is correct
52 Correct 2170 ms 136064 KB Output is correct
53 Correct 2168 ms 135304 KB Output is correct
54 Correct 2191 ms 135924 KB Output is correct
55 Correct 2049 ms 130944 KB Output is correct
56 Correct 2149 ms 134836 KB Output is correct
57 Correct 2414 ms 137540 KB Output is correct
58 Correct 2553 ms 147204 KB Output is correct
59 Correct 2553 ms 147496 KB Output is correct
60 Correct 2517 ms 146680 KB Output is correct
61 Correct 2599 ms 147456 KB Output is correct
62 Correct 2728 ms 146612 KB Output is correct
63 Correct 2652 ms 146596 KB Output is correct
64 Correct 2603 ms 138868 KB Output is correct
65 Correct 2648 ms 143156 KB Output is correct
66 Correct 1063 ms 74600 KB Output is correct
67 Correct 1332 ms 135576 KB Output is correct
68 Correct 1680 ms 140128 KB Output is correct
69 Correct 1584 ms 138840 KB Output is correct
70 Correct 2093 ms 145968 KB Output is correct
71 Correct 2177 ms 147140 KB Output is correct
72 Correct 2245 ms 148216 KB Output is correct
73 Correct 2297 ms 148428 KB Output is correct
74 Correct 988 ms 62332 KB Output is correct
75 Correct 1074 ms 83184 KB Output is correct
76 Correct 3395 ms 263488 KB Output is correct
77 Correct 3344 ms 260820 KB Output is correct
78 Correct 3502 ms 263072 KB Output is correct
79 Correct 2283 ms 148944 KB Output is correct
80 Correct 3932 ms 264552 KB Output is correct
81 Correct 2242 ms 148156 KB Output is correct
82 Execution timed out 4074 ms 265268 KB Time limit exceeded
83 Halted 0 ms 0 KB -