oj.uz

Submission #157488

# Submission time Handle Problem Language Result Execution time Memory
157488 2019-10-12T01:54:26 Z combi1k1 Street Lamps (APIO19_street_lamps) C++14
20 / 100
 1859 ms 83492 KB 
#include<bits/stdc++.h>

using namespace std;

#define X       first
#define Y       second
#define pb      emplace_back
#define mt      make_tuple
#define sz(x)   x.size()
#define all(x)  x.begin(),x.end()
#define ops     tuple<int,int,int>

const int   N   = 3e5 + 1;

typedef pair<int,int>   ii;

namespace  BIT  {
    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 > 0 ; x -= x & -x)
            val[x].push_back(y);
    }
    void upd(int x,int y,int v) {   //v < 0 -> turn on, v > 0 -> turn off
        for(; x > 0 ; 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 < N ; 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;
    }
};

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;

    S.insert({-1,-1});

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

    for(ii  e : S)  if (1 <= e.X && e.Y <= n)
        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] = n + 1 - x;
            r[i] = y - 1;
            continue;
        }
        if (on[x])  {
            ii  it = (*--S.upper_bound({x,x}));
            if (it.X < x)   S.insert({it.X,x - 1}), Q[i].pb(1,it.X,x - 1);
            if (it.Y > x)   S.insert({x + 1,it.Y}), Q[i].pb(1,x + 1,it.Y);
            S.erase(it);    Q[i].pb(0,it.X,it.Y);
        }
        if(!on[x])  {
            auto L = S.upper_bound({x,x});
            auto R = L--;
            int l = x;
            int r = x;
            if ((*R).X == x + 1)    {
                r = (*R).Y;
                S.erase(R);
                Q[i].pb(0,x + 1,r);
            }
            if ((*L).Y == x - 1)    {
                l = (*L).X;
                S.erase(L);
                Q[i].pb(0,l,x - 1);
            }
            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) = _;
        BIT::add(n + 1 - x,y);
    }

    BIT::ini(); Q[1].pb(1,n + 1,0);

    for(int i = 1 ; i <= q ; ++i)   {
        if (Q[i].empty())   {
            int ans = BIT::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)  BIT::upd(n + 1 - x,y,-i);
            else    BIT::upd(n + 1 - x,y, i);
        }
    }
}
/*
5 8
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
toggle 4
query 1 4
*/

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 31008 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 52 ms 43512 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 47 ms 31096 KB Output is correct
2 Correct 47 ms 30968 KB Output is correct
3 Correct 46 ms 30968 KB Output is correct
4 Correct 46 ms 30924 KB Output is correct
5 Correct 1859 ms 83492 KB Output is correct
6 Correct 1560 ms 76416 KB Output is correct
7 Correct 1192 ms 67076 KB Output is correct
8 Correct 299 ms 36060 KB Output is correct
9 Correct 166 ms 34296 KB Output is correct
10 Correct 184 ms 34420 KB Output is correct
11 Correct 177 ms 34656 KB Output is correct
12 Correct 284 ms 34168 KB Output is correct
13 Correct 300 ms 35960 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 30968 KB Output is correct
2 Correct 50 ms 31008 KB Output is correct
3 Incorrect 47 ms 30968 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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