oj.uz

Submission #157493

# Submission time Handle Problem Language Result Execution time Memory
157493 2019-10-12T02:53:14 Z combi1k1 Street Lamps (APIO19_street_lamps) C++14
20 / 100
 1993 ms 524292 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 < N ; 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 < 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;
    }
};

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] = 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(x,y);
    }

    BIT::ini(); Q[1].pb(1,N,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(x,y,-i);
            else    BIT::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 Runtime error 916 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 53 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 53 ms 31300 KB Output is correct
2 Correct 49 ms 31096 KB Output is correct
3 Correct 50 ms 31080 KB Output is correct
4 Correct 46 ms 30952 KB Output is correct
5 Correct 1993 ms 88108 KB Output is correct
6 Correct 1739 ms 80396 KB Output is correct
7 Correct 1309 ms 70216 KB Output is correct
8 Correct 289 ms 37496 KB Output is correct
9 Correct 137 ms 36216 KB Output is correct
10 Correct 152 ms 36428 KB Output is correct
11 Correct 145 ms 36468 KB Output is correct
12 Correct 268 ms 35932 KB Output is correct
13 Correct 340 ms 37572 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 30924 KB Output is correct
2 Correct 47 ms 31064 KB Output is correct
3 Incorrect 50 ms 31164 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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