oj.uz

Submission #166623

# Submission time Handle Problem Language Result Execution time Memory
166623 2019-12-03T07:30:21 Z combi1k1 Street Lamps (APIO19_street_lamps) C++14
20 / 100
 2163 ms 90040 KB 
#include<bits/stdc++.h>

using namespace std;

#define X       first
#define Y       second

#define pb      emplace_back

#define sz(x)   x.size()
#define all(x)  x.begin(),x.end()

#define ops     tuple<int,int,int>

const int   N   = 3e5 + 5;

typedef pair<int,int>   ii;

namespace BIT2D {
    vector<int> val[N];
    vector<int> bit[N];

    void ini() {
        for(int i = 1 ; i < N ; ++i)    {
            sort(all(val[i]));
            val[i].resize(unique(all(val[i])) - val[i].begin());
            bit[i].resize(sz(val[i]) + 5);
        }
    }
    void add(int x,int y)   {
        for(; x < N ; x += x & -x)
            val[x].push_back(y);
    }
    void upd(int x,int y,int v) {
        for(; x < N ; x += x & -x)  {
            int p = lower_bound(all(val[x]),y) - val[x].begin() + 1;
            for(; p > 0 ; p -= p & -p)
                bit[x][p] += v;
        }
    }
    int get(int x,int y)    {
        int ans = 0;
        for(; x > 0 ; x -= x & -x)  {
            int p = lower_bound(all(val[x]),y) - val[x].begin() + 1;
            int K = sz(bit[x]);
            for(; p < K ; p += p & -p)
                ans += bit[x][p];
        }
        return  ans;
    }
}

using BIT2D::upd;
using BIT2D::get;

bool on[N];
set<ii> S;

vector<ops> Q[N];
int l[N];
int r[N];

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;
    int q;  cin >> q;   ++q;

    for(int i = 1 ; i <= n ; ++i)   {
        char c; cin >> c;
        if (c == '1')   {
            if (on[i - 1])  {
                ii  seg = (*--S.end());
                S.erase (seg);  seg.Y = i;
                S.insert(seg);
            }
            else
                S.insert(ii(i,i));

            on[i] = 1;
        }
    }
    for(ii  e : S)  Q[1].pb(1,e.X,e.Y);

    string t;

    for(int i = 2 ; i <= q ; ++i)   {
        int x, y;   cin >> t >> x;

        if (t == "query")   {
            cin >> y;
            l[i] = x;
            r[i] = y - 1;
            continue;
        }
        if (on[x])  {
            auto it = S.upper_bound(ii(x,x));
            ii  range = (*--it);
            int L = range.X;
            int R = range.Y;
            if (L < x)  S.insert(ii(L,x - 1)),  Q[i].pb(1,L,x - 1);
            if (R > x)  S.insert(ii(x + 1,R)),  Q[i].pb(1,x + 1,R);

            S.erase(range); Q[i].pb(0,L,R);
        }
        else    {
            int l = x;
            int r = x;

            if (on[x + 1])  {
                auto  it = S.upper_bound(ii(x,x));
                r = (*it).Y;
                Q[i].pb(0,x + 1,r);
                S.erase(it);
            }
            if (on[x - 1])  {
                auto  it = S.upper_bound(ii(x,x));   --it;
                l = (*it).X;
                Q[i].pb(0,l,x - 1);
                S.erase(it);
            }
            S.insert({l,r});
            Q[i].pb(1,l,r);
        }
        on[x] ^= 1;
    }

    for(int i = 1 ; i <= q ; ++i)
    for(ops _ : Q[i])   {
        int v, x, y;
        tie(v, x, y) = _;
        BIT2D::add(x,y);
    }

    BIT2D::ini();   Q[1].pb(1,N,0);

    for(int i = 1 ; i <= q ; ++i)   {
        if (Q[i].empty())   {
            int ans = get(l[i],r[i]);
            if (ans < 0)
                ans += i;
            cout << ans << "\n";
        }
        for(ops _ : Q[i])   {
            int v, x, y;
            tie(v, x, y) = _;
            if (v)  upd(x,y,-i);
            else    upd(x,y, i);
        }
    }
}
/*
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 43908 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 31224 KB Output is correct
2 Correct 52 ms 31096 KB Output is correct
3 Correct 51 ms 31096 KB Output is correct
4 Correct 49 ms 31068 KB Output is correct
5 Correct 2163 ms 90040 KB Output is correct
6 Correct 1872 ms 83352 KB Output is correct
7 Correct 1422 ms 73628 KB Output is correct
8 Correct 337 ms 41592 KB Output is correct
9 Correct 141 ms 36472 KB Output is correct
10 Correct 150 ms 36984 KB Output is correct
11 Correct 149 ms 37244 KB Output is correct
12 Correct 294 ms 39848 KB Output is correct
13 Correct 309 ms 41564 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

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