oj.uz

Submission #158307

# Submission time Handle Problem Language Result Execution time Memory
158307 2019-10-16T08:51:11 Z combi1k1 Street Lamps (APIO19_street_lamps) C++14
20 / 100
 1904 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 X = x, Y = 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])  {
        	auto it = S.upper_bound({x,x});
        	ii  range = (*--it);
        	int L = range.X;
        	int R = range.Y;
        	if (L < x)	S.insert({L,x - 1}), Q[i].pb(1,L,x - 1);
        	if (R > x)	S.insert({x + 1,R}), Q[i].pb(1,x + 1,R);
        	S.erase(range); Q[i].pb(0,L,R);
        }
        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
*/

Compilation message

street_lamps.cpp: In function 'int BIT::get(int, int)':
street_lamps.cpp:5:17: warning: unused variable 'first' [-Wunused-variable]
 #define X       first
                 ^
street_lamps.cpp:40:13: note: in expansion of macro 'X'
         int X = x, Y = y;
             ^
street_lamps.cpp:6:17: warning: unused variable 'second' [-Wunused-variable]
 #define Y       second
                 ^
street_lamps.cpp:40:20: note: in expansion of macro 'Y'
         int X = x, Y = y;
                    ^

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 958 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 54 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 51 ms 31096 KB Output is correct
2 Correct 48 ms 31116 KB Output is correct
3 Correct 47 ms 31068 KB Output is correct
4 Correct 45 ms 30840 KB Output is correct
5 Correct 1904 ms 89956 KB Output is correct
6 Correct 1762 ms 83080 KB Output is correct
7 Correct 1341 ms 73600 KB Output is correct
8 Correct 275 ms 41500 KB Output is correct
9 Correct 137 ms 36476 KB Output is correct
10 Correct 148 ms 36984 KB Output is correct
11 Correct 146 ms 37112 KB Output is correct
12 Correct 259 ms 39764 KB Output is correct
13 Correct 295 ms 41464 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 30900 KB Output is correct
2 Correct 51 ms 31068 KB Output is correct
3 Incorrect 52 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 Runtime error 958 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -