oj.uz

Submission #157482

# Submission time Handle Problem Language Result Execution time Memory
157482 2019-10-12T00:17:31 Z combi1k1 Street Lamps (APIO19_street_lamps) C++14
20 / 100
 1859 ms 99200 KB 
#include<bits/stdc++.h>

using namespace std;

#define ll      long long
#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<ii>  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 off, v > 0 -> turn on
        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].X += v,
                bit[x][p].Y ^= 1;
        }
    }
    ii  get(int x,int y)    {
        ii  ans(0,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.X += bit[x][p].X,
                ans.Y ^= bit[x][p].Y;
        }
        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;

    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[0].pb(1,e.X,e.Y);

    string t;
    for(int i = 1 ; i <= q ; ++i)   {
        int x, y;   cin >> t >> x;
        if (t == "query")   {
            cin >> y;
            l[i] = n - x + 1;
            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 = 0 ; i <= q ; ++i)
    for(ops _ : Q[i])   {
        int v, x, y;
        tie(v, x, y) = _;
        BIT::add(n + 1 - x,y);
    }

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

    for(int i = 0 ; i <= q ; ++i)   {
        if (Q[i].empty())   {
            ii  res = BIT::get(l[i],r[i]);
            int ans = res.X;
            if (res.Y)
                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 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 47 ms 35576 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 43516 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 50 ms 35704 KB Output is correct
2 Correct 49 ms 35704 KB Output is correct
3 Correct 50 ms 35832 KB Output is correct
4 Correct 53 ms 35704 KB Output is correct
5 Correct 1859 ms 99200 KB Output is correct
6 Correct 1621 ms 92584 KB Output is correct
7 Correct 1237 ms 81952 KB Output is correct
8 Correct 294 ms 46200 KB Output is correct
9 Correct 175 ms 41196 KB Output is correct
10 Correct 192 ms 41976 KB Output is correct
11 Correct 186 ms 41848 KB Output is correct
12 Correct 290 ms 44468 KB Output is correct
13 Correct 303 ms 46224 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 35792 KB Output is correct
2 Correct 48 ms 35704 KB Output is correct
3 Incorrect 49 ms 35808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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