oj.uz

Submission #170166

# Submission time Handle Problem Language Result Execution time Memory
170166 2019-12-24T06:34:37 Z arnold518 Street Lamps (APIO19_street_lamps) C++14
100 / 100
 4769 ms 428604 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
{
    pll val;
    Node1 *lc, *rc;
    Node1() : lc(NULL), rc(NULL) {}
};
Node1 *tree[MAXN+10];

void update1(Node1 *node, int tl, int tr, int x, pll val)
{
    node->val=node->val+val;
    if(tl==tr) return;
    int mid=tl+tr>>1;
    if(x<=mid)
    {
        if(node->lc==NULL) node->lc=new Node1();
        update1(node->lc, tl, mid, x, val);
    }
    else
    {
        if(node->rc==NULL) node->rc=new Node1();
        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;
    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:46: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:55: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:61:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:69:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
street_lamps.cpp:71: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:72: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:86:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", st);
         ~~~~~^~~~~~~~~~
street_lamps.cpp:89:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &a);
             ~~~~~^~~~~~~~~~
street_lamps.cpp:155: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 376 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 285 ms 3192 KB Output is correct
2 Correct 367 ms 4532 KB Output is correct
3 Correct 886 ms 12348 KB Output is correct
4 Correct 3125 ms 366404 KB Output is correct
5 Correct 3140 ms 333640 KB Output is correct
6 Correct 3550 ms 381496 KB Output is correct
7 Correct 273 ms 24440 KB Output is correct
8 Correct 288 ms 25976 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 3 ms 376 KB Output is correct
5 Correct 4769 ms 428604 KB Output is correct
6 Correct 4286 ms 408808 KB Output is correct
7 Correct 2673 ms 332628 KB Output is correct
8 Correct 291 ms 25848 KB Output is correct
9 Correct 111 ms 4088 KB Output is correct
10 Correct 119 ms 4344 KB Output is correct
11 Correct 122 ms 4596 KB Output is correct
12 Correct 315 ms 24416 KB Output is correct
13 Correct 316 ms 26036 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 4 ms 888 KB Output is correct
3 Correct 5 ms 1016 KB Output is correct
4 Correct 5 ms 1144 KB Output is correct
5 Correct 889 ms 261616 KB Output is correct
6 Correct 1932 ms 331184 KB Output is correct
7 Correct 3060 ms 380544 KB Output is correct
8 Correct 4540 ms 428452 KB Output is correct
9 Correct 417 ms 4596 KB Output is correct
10 Correct 356 ms 3588 KB Output is correct
11 Correct 413 ms 4604 KB Output is correct
12 Correct 355 ms 3504 KB Output is correct
13 Correct 419 ms 4620 KB Output is correct
14 Correct 355 ms 3580 KB Output is correct
15 Correct 270 ms 24492 KB Output is correct
16 Correct 288 ms 25976 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 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 285 ms 3192 KB Output is correct
9 Correct 367 ms 4532 KB Output is correct
10 Correct 886 ms 12348 KB Output is correct
11 Correct 3125 ms 366404 KB Output is correct
12 Correct 3140 ms 333640 KB Output is correct
13 Correct 3550 ms 381496 KB Output is correct
14 Correct 273 ms 24440 KB Output is correct
15 Correct 288 ms 25976 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 3 ms 376 KB Output is correct
20 Correct 4769 ms 428604 KB Output is correct
21 Correct 4286 ms 408808 KB Output is correct
22 Correct 2673 ms 332628 KB Output is correct
23 Correct 291 ms 25848 KB Output is correct
24 Correct 111 ms 4088 KB Output is correct
25 Correct 119 ms 4344 KB Output is correct
26 Correct 122 ms 4596 KB Output is correct
27 Correct 315 ms 24416 KB Output is correct
28 Correct 316 ms 26036 KB Output is correct
29 Correct 3 ms 760 KB Output is correct
30 Correct 4 ms 888 KB Output is correct
31 Correct 5 ms 1016 KB Output is correct
32 Correct 5 ms 1144 KB Output is correct
33 Correct 889 ms 261616 KB Output is correct
34 Correct 1932 ms 331184 KB Output is correct
35 Correct 3060 ms 380544 KB Output is correct
36 Correct 4540 ms 428452 KB Output is correct
37 Correct 417 ms 4596 KB Output is correct
38 Correct 356 ms 3588 KB Output is correct
39 Correct 413 ms 4604 KB Output is correct
40 Correct 355 ms 3504 KB Output is correct
41 Correct 419 ms 4620 KB Output is correct
42 Correct 355 ms 3580 KB Output is correct
43 Correct 270 ms 24492 KB Output is correct
44 Correct 288 ms 25976 KB Output is correct
45 Correct 106 ms 2780 KB Output is correct
46 Correct 180 ms 2964 KB Output is correct
47 Correct 1333 ms 132680 KB Output is correct
48 Correct 2909 ms 366368 KB Output is correct
49 Correct 134 ms 4600 KB Output is correct
50 Correct 130 ms 4472 KB Output is correct
51 Correct 138 ms 4728 KB Output is correct
52 Correct 142 ms 5108 KB Output is correct
53 Correct 142 ms 5252 KB Output is correct
54 Correct 143 ms 5116 KB Output is correct