oj.uz

Submission #170207

# Submission time Handle Problem Language Result Execution time Memory
170207 2019-12-24T08:41:34 Z arnold518 Street Lamps (APIO19_street_lamps) C++14
100 / 100
 1830 ms 67848 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 Data
{
    int t, y, x; pll val;
    bool operator < (const Data &p) const { return x<p.x; }
};
vector<Data> todo;

struct BIT
{
    pll tree[MAXN+10];
    void update(int i, pll v) { for(; i<=N; i+=(i&-i)) tree[i]=tree[i]+v; }
    pll query(int i) { pll ret(0, 0); for(; i>0; i-=(i&-i)) ret=ret+tree[i]; return ret; }
    void flush(int i) { for(; i<=N; i+=(i&-i)) tree[i]=pll(0, 0); }
}bit;

void update(int y, int x, pll v) { todo.push_back({0, N-y+1, x, v}); }
void query(int y, int x, ll v) { todo.push_back({0, 0, 0, {0, 0}}); todo.back()={1, N-y+1, x, {v, todo.size()-1}}; }

pll ans[MAXN*10+10];

void solve(int s, int e)
{
    int i, j;
    if(s==e)
    {
        if(todo[s].t)
        {
            pll ret=ans[s];
            printf("%lld\n", ret.first-ret.second*todo[s].val.first);
        }
        return;
    }

    int mid=s+e>>1;
    solve(s, mid);

    vector<Data> A, B;
    for(i=s; i<=mid; i++) if(!todo[i].t) A.push_back(todo[i]);
    for(i=mid+1; i<=e; i++) if(todo[i].t) B.push_back(todo[i]);

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    for(i=0, j=0; i<B.size(); i++)
    {
        for(; j<A.size() && A[j].x<=B[i].x; j++) bit.update(A[j].y, A[j].val);
        ans[B[i].val.second]=ans[B[i].val.second]+bit.query(B[i].y);
    }
    for(j=0; j<A.size(); j++) bit.flush(A[j].y);

    solve(mid+1, e);
}

int main()
{
    int i, j;

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

    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++) update(*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())
                {
                    update(range(a-1).second, range(a-1).first, pll(-(Q-i+1), -1));
                    update(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())
                {
                    update(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())
                {
                    update(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);
                }
                update(range(a).second, range(a).first, pll((Q-i+1), 1));
                A[a]=1;
            }
            else
            {
                int s, e;
                tie(s, e)=range(a);

                update(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);
                    update(range(a+1).second, range(a+1).first, pll((Q-i+1), 1));
                }
                else if(e==a)
                {
                    E.erase(a);
                    E.insert(a-1);
                    update(range(a-1).second, range(a-1).first, pll((Q-i+1), 1));
                }
                else
                {
                    S.insert(a+1);
                    E.insert(a-1);
                    update(range(a-1).second, range(a-1).first, pll((Q-i+1), 1));
                    update(range(a+1).second, range(a+1).first, pll((Q-i+1), 1));
                }
                A[a]=0;
            }
        }
        else
        {
            scanf("%d%d", &a, &b); b--;
            query(b, a, Q-i+1);
        }
    }

    solve(0, todo.size()-1);
}

Compilation message

street_lamps.cpp: In function 'void solve(int, int)':
street_lamps.cpp:50:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=s+e>>1;
             ~^~
street_lamps.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0, j=0; i<B.size(); i++)
                   ~^~~~~~~~~
street_lamps.cpp:62:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(; j<A.size() && A[j].x<=B[i].x; j++) bit.update(A[j].y, A[j].val);
               ~^~~~~~~~~
street_lamps.cpp:65:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j=0; j<A.size(); j++) bit.flush(A[j].y);
              ~^~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:72:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
street_lamps.cpp:74: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:75: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:88:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", st);
         ~~~~~^~~~~~~~~~
street_lamps.cpp:91:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &a);
             ~~~~~^~~~~~~~~~
street_lamps.cpp:157: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 380 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 711 ms 39988 KB Output is correct
2 Correct 774 ms 42812 KB Output is correct
3 Correct 876 ms 43756 KB Output is correct
4 Correct 1404 ms 59612 KB Output is correct
5 Correct 1440 ms 57768 KB Output is correct
6 Correct 1356 ms 67848 KB Output is correct
7 Correct 486 ms 29500 KB Output is correct
8 Correct 497 ms 30896 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 3 ms 380 KB Output is correct
5 Correct 1760 ms 62420 KB Output is correct
6 Correct 1733 ms 67004 KB Output is correct
7 Correct 1360 ms 53396 KB Output is correct
8 Correct 497 ms 30780 KB Output is correct
9 Correct 231 ms 22884 KB Output is correct
10 Correct 266 ms 28840 KB Output is correct
11 Correct 263 ms 28604 KB Output is correct
12 Correct 491 ms 29488 KB Output is correct
13 Correct 505 ms 31128 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 592 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 5 ms 632 KB Output is correct
5 Correct 698 ms 47456 KB Output is correct
6 Correct 1084 ms 57368 KB Output is correct
7 Correct 1433 ms 65060 KB Output is correct
8 Correct 1830 ms 67292 KB Output is correct
9 Correct 760 ms 44960 KB Output is correct
10 Correct 818 ms 49708 KB Output is correct
11 Correct 760 ms 45008 KB Output is correct
12 Correct 830 ms 49696 KB Output is correct
13 Correct 757 ms 44736 KB Output is correct
14 Correct 825 ms 49736 KB Output is correct
15 Correct 488 ms 29508 KB Output is correct
16 Correct 499 ms 30860 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 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 711 ms 39988 KB Output is correct
9 Correct 774 ms 42812 KB Output is correct
10 Correct 876 ms 43756 KB Output is correct
11 Correct 1404 ms 59612 KB Output is correct
12 Correct 1440 ms 57768 KB Output is correct
13 Correct 1356 ms 67848 KB Output is correct
14 Correct 486 ms 29500 KB Output is correct
15 Correct 497 ms 30896 KB Output is correct
16 Correct 5 ms 504 KB Output is correct
17 Correct 5 ms 632 KB Output is correct
18 Correct 4 ms 504 KB Output is correct
19 Correct 3 ms 380 KB Output is correct
20 Correct 1760 ms 62420 KB Output is correct
21 Correct 1733 ms 67004 KB Output is correct
22 Correct 1360 ms 53396 KB Output is correct
23 Correct 497 ms 30780 KB Output is correct
24 Correct 231 ms 22884 KB Output is correct
25 Correct 266 ms 28840 KB Output is correct
26 Correct 263 ms 28604 KB Output is correct
27 Correct 491 ms 29488 KB Output is correct
28 Correct 505 ms 31128 KB Output is correct
29 Correct 3 ms 504 KB Output is correct
30 Correct 4 ms 592 KB Output is correct
31 Correct 4 ms 632 KB Output is correct
32 Correct 5 ms 632 KB Output is correct
33 Correct 698 ms 47456 KB Output is correct
34 Correct 1084 ms 57368 KB Output is correct
35 Correct 1433 ms 65060 KB Output is correct
36 Correct 1830 ms 67292 KB Output is correct
37 Correct 760 ms 44960 KB Output is correct
38 Correct 818 ms 49708 KB Output is correct
39 Correct 760 ms 45008 KB Output is correct
40 Correct 830 ms 49696 KB Output is correct
41 Correct 757 ms 44736 KB Output is correct
42 Correct 825 ms 49736 KB Output is correct
43 Correct 488 ms 29508 KB Output is correct
44 Correct 499 ms 30860 KB Output is correct
45 Correct 368 ms 24820 KB Output is correct
46 Correct 468 ms 25428 KB Output is correct
47 Correct 747 ms 31496 KB Output is correct
48 Correct 1360 ms 57696 KB Output is correct
49 Correct 303 ms 30720 KB Output is correct
50 Correct 299 ms 30708 KB Output is correct
51 Correct 297 ms 30652 KB Output is correct
52 Correct 296 ms 28388 KB Output is correct
53 Correct 301 ms 28428 KB Output is correct
54 Correct 299 ms 28224 KB Output is correct