oj.uz

Submission #170175

# Submission time Handle Problem Language Result Execution time Memory
170175 2019-12-24T07:04:28 Z arnold518 Street Lamps (APIO19_street_lamps) C++14
100 / 100
 4388 ms 427588 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3e5;

int N, Q, A[MAXN+10];

set<int> S, E;
pii range(int x) { return pii(*(--S.upper_bound(x)), *E.lower_bound(x)); }

pll operator + (const pll &p, const pll &q) { return pll(p.first+q.first, p.second+q.second); }

struct Node1
{
    int pos; pll val;
    Node1 *lc, *rc;
    Node1() : pos(-1), lc(NULL), rc(NULL) {}
};
Node1 *tree[MAXN+10];

void update1(Node1 *node, int tl, int tr, int x, pll val)
{
    if(tl==tr) { node->val=node->val+val; return; }

    int mid=tl+tr>>1;
    if(node->pos!=-1)
    {
        if(node->pos<=mid)
        {
            node->lc=new Node1();
            node->lc->val=node->val;
            node->lc->pos=node->pos;
        }
        else
        {
            node->rc=new Node1();
            node->rc->val=node->val;
            node->rc->pos=node->pos;
        }
        node->pos=-1;
    }

    node->val=node->val+val;
    if(x<=mid)
    {
        if(node->lc==NULL)
        {
            node->lc=new Node1();
            node->lc->val=val;
            node->lc->pos=x;
        }
        else update1(node->lc, tl, mid, x, val);
    }
    else
    {
        if(node->rc==NULL)
        {
            node->rc=new Node1();
            node->rc->val=val;
            node->rc->pos=x;
        }
        else update1(node->rc, mid+1, tr, x, val);
    }
}

pll query1(Node1 *node, int tl, int tr, int l, int r)
{
    if(tr<l || r<tl) return pll(0, 0);
    if(l<=tl && tr<=r) return node->val;
    int mid=tl+tr>>1;
    if(node->pos!=-1)
    {
        if(l<=node->pos && node->pos<=r) return node->val;
        else return pll(0, 0);
    }
    pll ret(0, 0);
    if(node->lc!=NULL) ret=ret+query1(node->lc, tl, mid, l, r);
    if(node->rc!=NULL) ret=ret+query1(node->rc, mid+1, tr, l, r);
    return ret;
}

void update2(int y, int x, pll val)
{
    int i, j; y=N-y+1;
    for(i=y; i<=N; i+=(i&-i)) update1(tree[i], 1, N, x, val);
}

pll query2(int y, int x)
{
    int i, j;
    pll ret(0, 0); y=N-y+1;
    for(i=y; i>0; i-=(i&-i)) ret=ret+query1(tree[i], 1, N, 1, x);
    return ret;
}

int main()
{
    int i, j;

    scanf("%d%d", &N, &Q);
    for(i=1; i<=N; i++) scanf("%1d", &A[i]);
    for(i=1; i<=N; i++) tree[i]=new Node1();

    set<int>::iterator it, jt;
    for(i=1; i<=N; i++) if(A[i-1]==0 && A[i]==1) S.insert(i);
    for(i=1; i<=N; i++) if(A[i]==1 && A[i+1]==0) E.insert(i);

    for(it=S.begin(), jt=E.begin(); it!=S.end() && jt!=E.end(); it++, jt++) update2(*jt, *it, pll(Q+1, 1));

    for(i=1; i<=Q; i++)
    {
        char st[10];
        int a, b;

        scanf("%s", st);
        if(st[0]=='t')
        {
            scanf("%d", &a);

            if(A[a]==0)
            {
                if(S.find(a+1)!=S.end() && E.find(a-1)!=E.end())
                {
                    update2(range(a-1).second, range(a-1).first, pll(-(Q-i+1), -1));
                    update2(range(a+1).second, range(a+1).first, pll(-(Q-i+1), -1));
                    S.erase(a+1);
                    E.erase(a-1);
                }
                else if(S.find(a+1)!=S.end())
                {
                    update2(range(a+1).second, range(a+1).first, pll(-(Q-i+1), -1));
                    S.erase(a+1);
                    S.insert(a);
                }
                else if(E.find(a-1)!=E.end())
                {
                    update2(range(a-1).second, range(a-1).first, pll(-(Q-i+1), -1));
                    E.erase(a-1);
                    E.insert(a);
                }
                else
                {
                    S.insert(a);
                    E.insert(a);
                }
                update2(range(a).second, range(a).first, pll((Q-i+1), 1));
                A[a]=1;
            }
            else
            {
                int s, e;
                tie(s, e)=range(a);

                update2(range(a).second, range(a).first, pll(-(Q-i+1), -1));
                if(s==e)
                {
                    S.erase(a);
                    E.erase(a);
                }
                else if(s==a)
                {
                    S.erase(a);
                    S.insert(a+1);
                    update2(range(a+1).second, range(a+1).first, pll((Q-i+1), 1));
                }
                else if(e==a)
                {
                    E.erase(a);
                    E.insert(a-1);
                    update2(range(a-1).second, range(a-1).first, pll((Q-i+1), 1));
                }
                else
                {
                    S.insert(a+1);
                    E.insert(a-1);
                    update2(range(a-1).second, range(a-1).first, pll((Q-i+1), 1));
                    update2(range(a+1).second, range(a+1).first, pll((Q-i+1), 1));
                }
                A[a]=0;
            }
        }
        else
        {
            scanf("%d%d", &a, &b); b--;
            pll ret=query2(b, a);
            printf("%lld\n", ret.first-ret.second*(Q-i+1));
        }
    }
}

Compilation message

street_lamps.cpp: In function 'void update1(Node1*, int, int, int, pll)':
street_lamps.cpp:29:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
street_lamps.cpp: In function 'pll query1(Node1*, int, int, int, int)':
street_lamps.cpp:74:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
street_lamps.cpp: In function 'void update2(int, int, pll)':
street_lamps.cpp:88:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j; y=N-y+1;
            ^
street_lamps.cpp: In function 'pll query2(int, int)':
street_lamps.cpp:94:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:102:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
street_lamps.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &Q);
     ~~~~~^~~~~~~~~~~~~~~~
street_lamps.cpp:105:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=N; i++) scanf("%1d", &A[i]);
                         ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:119:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", st);
         ~~~~~^~~~~~~~~~
street_lamps.cpp:122:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &a);
             ~~~~~^~~~~~~~~~
street_lamps.cpp:188:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &a, &b); b--;
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 1528 KB Output is correct
2 Correct 394 ms 4084 KB Output is correct
3 Correct 918 ms 13020 KB Output is correct
4 Correct 2989 ms 314636 KB Output is correct
5 Correct 3086 ms 332652 KB Output is correct
6 Correct 3258 ms 338816 KB Output is correct
7 Correct 278 ms 18564 KB Output is correct
8 Correct 288 ms 20032 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1144 KB Output is correct
2 Correct 5 ms 1144 KB Output is correct
3 Correct 4 ms 1016 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 4253 ms 427588 KB Output is correct
6 Correct 3656 ms 408184 KB Output is correct
7 Correct 2481 ms 332276 KB Output is correct
8 Correct 284 ms 20216 KB Output is correct
9 Correct 110 ms 1400 KB Output is correct
10 Correct 120 ms 1372 KB Output is correct
11 Correct 122 ms 1652 KB Output is correct
12 Correct 267 ms 18808 KB Output is correct
13 Correct 289 ms 20080 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 4 ms 760 KB Output is correct
3 Correct 5 ms 1016 KB Output is correct
4 Correct 5 ms 1056 KB Output is correct
5 Correct 660 ms 127200 KB Output is correct
6 Correct 1765 ms 262500 KB Output is correct
7 Correct 2966 ms 338460 KB Output is correct
8 Correct 4388 ms 402936 KB Output is correct
9 Correct 448 ms 1544 KB Output is correct
10 Correct 372 ms 604 KB Output is correct
11 Correct 448 ms 1400 KB Output is correct
12 Correct 373 ms 760 KB Output is correct
13 Correct 443 ms 1608 KB Output is correct
14 Correct 373 ms 760 KB Output is correct
15 Correct 272 ms 18680 KB Output is correct
16 Correct 292 ms 20048 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 298 ms 1528 KB Output is correct
9 Correct 394 ms 4084 KB Output is correct
10 Correct 918 ms 13020 KB Output is correct
11 Correct 2989 ms 314636 KB Output is correct
12 Correct 3086 ms 332652 KB Output is correct
13 Correct 3258 ms 338816 KB Output is correct
14 Correct 278 ms 18564 KB Output is correct
15 Correct 288 ms 20032 KB Output is correct
16 Correct 5 ms 1144 KB Output is correct
17 Correct 5 ms 1144 KB Output is correct
18 Correct 4 ms 1016 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 4253 ms 427588 KB Output is correct
21 Correct 3656 ms 408184 KB Output is correct
22 Correct 2481 ms 332276 KB Output is correct
23 Correct 284 ms 20216 KB Output is correct
24 Correct 110 ms 1400 KB Output is correct
25 Correct 120 ms 1372 KB Output is correct
26 Correct 122 ms 1652 KB Output is correct
27 Correct 267 ms 18808 KB Output is correct
28 Correct 289 ms 20080 KB Output is correct
29 Correct 3 ms 504 KB Output is correct
30 Correct 4 ms 760 KB Output is correct
31 Correct 5 ms 1016 KB Output is correct
32 Correct 5 ms 1056 KB Output is correct
33 Correct 660 ms 127200 KB Output is correct
34 Correct 1765 ms 262500 KB Output is correct
35 Correct 2966 ms 338460 KB Output is correct
36 Correct 4388 ms 402936 KB Output is correct
37 Correct 448 ms 1544 KB Output is correct
38 Correct 372 ms 604 KB Output is correct
39 Correct 448 ms 1400 KB Output is correct
40 Correct 373 ms 760 KB Output is correct
41 Correct 443 ms 1608 KB Output is correct
42 Correct 373 ms 760 KB Output is correct
43 Correct 272 ms 18680 KB Output is correct
44 Correct 292 ms 20048 KB Output is correct
45 Correct 107 ms 936 KB Output is correct
46 Correct 192 ms 1016 KB Output is correct
47 Correct 1339 ms 124696 KB Output is correct
48 Correct 2598 ms 317568 KB Output is correct
49 Correct 130 ms 1144 KB Output is correct
50 Correct 131 ms 1124 KB Output is correct
51 Correct 133 ms 1144 KB Output is correct
52 Correct 141 ms 1272 KB Output is correct
53 Correct 143 ms 1144 KB Output is correct
54 Correct 142 ms 1200 KB Output is correct