oj.uz

Submission #212635

# Submission time Handle Problem Language Result Execution time Memory
212635 2020-03-23T21:34:43 Z VEGAnn Street Lamps (APIO19_street_lamps) C++14
100 / 100
 2721 ms 319088 KB 
#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define PB push_back
#define MP make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define pdd pair<ld, ld>
#define ft first
#define sd second
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
template<class T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const int N = 300100;
const int M = 2 * N;
const int oo = 2e9;
const ll OO = 1e18;
const int md = 998244353;
const int PW = 233;
set<pii> st;
set<pii>::iterator ite;
vector<pii> qr, pts;
string qu, s;
int q, n;
bool state[N];

struct seg_tree{
    vector<int> ys;
    vector<ll> st;

    seg_tree(): ys(0), st(0) {}

    void update(int v, int l, int r, int y, int vl){
        if (ys[l] > y) return;

        if (ys[r] <= y) {
            st[v] += vl;
            return;
        }

        if (l == r) return;

        int md = (l + r) >> 1;
        update(v + v, l, md, y, vl);
        update(v + v + 1, md + 1, r, y, vl);
    }

    ll get(int v, int l, int r, int y){
        ll res = st[v];

        if (l == r) return res;

        int md = (l + r) >> 1;

        if (ys[md + 1] <= y)
            res += get(v + v + 1, md + 1, r, y);
        else res += get(v + v, l, md, y);

        return res;
    }
};

seg_tree seg[4 * N];

void build(int v, int l, int r){
    if (l == r){
        seg[v].ys.PB(pts[l].sd);
        seg[v].st.resize(2);
        return;
    }

    int md = (l + r) >> 1;
    build(v + v, l, md);
    build(v + v + 1, md + 1, r);

    merge(all(seg[v + v].ys), all(seg[v + v + 1].ys), back_inserter(seg[v].ys));
    seg[v].st.resize(sz(seg[v].ys) * 4 + 3);
}

void update(int v, int l, int r, int min_x, int max_y, int vl){
    if (pts[r].ft < min_x) return;

    if (pts[l].ft >= min_x) {
        seg[v].update(1, 0, sz(seg[v].ys) - 1, max_y, vl);
        return;
    }

    if (l == r) return;

    int md = (l + r) >> 1;

    update(v + v, l, md, min_x, max_y, vl);
    update(v + v + 1, md + 1, r, min_x, max_y, vl);
}

ll get(int v, int l, int r, int min_x, int max_y){
    ll res = seg[v].get(1, 0, sz(seg[v].ys) - 1, max_y);

    if (l == r) return res;

    int md = (l + r) >> 1;

    if (MP(min_x, max_y) <= pts[md])
        res += get(v + v, l, md, min_x, max_y);
    else res += get(v + v + 1, md + 1, r, min_x, max_y);

    return res;
}

int main() {
#ifdef _LOCAL
//    freopen("in.txt","r",stdin); // freopen("output.txt","w",stdout);
#else
//    freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(0); cin.tie(0);
#endif

    cin >> n >> q >> s;

    for (int i = 0; i < n; i++)
        state[i] = s[i] - '0';

    for (int i = 0; i < q; i++){
        cin >> qu;

        if (qu[0] == 'q'){
            int x, y; cin >> x >> y;
            x--; y--;
            qr.PB(MP(x, y));
            pts.PB(MP(x, y));
        } else {
            int x; cin >> x;
            x--;

            qr.PB(MP(x, -228));
        }
    }

    sort(all(pts));
    pts.resize(unique(all(pts)) - pts.begin());

    build(1, 0, sz(pts) - 1);

    for (int i = 0; i <= n;){
        int j = i;
        while (j < n && state[j])
            j++;

        st.insert(MP(i, j));
        i = j + 1;
    }

//    for (pii cr : pts)
//        cerr << cr.ft << " " << cr.sd << '\n';

    int tim = 1;

    for (pii cr : qr) {

//
//        for (auto x : st)
//            cerr << x.ft << " " << x.sd << '\n';
//        cerr << "\n\n";

        if (cr.sd == -228){
            int i = cr.ft;

            if (!state[i]){
                ite = prev(st.upper_bound(MP(i + 1, oo)));
                int lf = (*prev(ite)).ft;
                int rt = (*ite).sd;

                st.erase(MP(lf, i));
                st.erase(MP(i + 1, rt));
                st.insert(MP(lf, rt));

                update(1, 0, sz(pts) - 1, lf, rt, -tim);
                update(1, 0, sz(pts) - 1, lf, i, tim);
                update(1, 0, sz(pts) - 1, i + 1, rt, tim);
            } else {
                pii segm = *(prev(st.upper_bound(MP(i + 1, -oo))));

                st.erase(segm);
                st.insert(MP(segm.ft, i));
                st.insert(MP(i + 1, segm.sd));

                update(1, 0, sz(pts) - 1, segm.ft, segm.sd, tim);
                update(1, 0, sz(pts) - 1, segm.ft, i, -tim);
                update(1, 0, sz(pts) - 1, i + 1, segm.sd, -tim);
            }

            state[i] ^= 1;
        } else {
            ll res = get(1, 0, sz(pts)  - 1, cr.ft, cr.sd);

            pii segm = *prev(st.upper_bound(MP(cr.ft, oo)));

            if (segm.ft <= cr.ft && segm.sd >= cr.sd)
                res += tim;

            cout << res << '\n';
        }

        tim++;
    }

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 56704 KB Output is correct
2 Correct 37 ms 56704 KB Output is correct
3 Correct 35 ms 56696 KB Output is correct
4 Correct 35 ms 56696 KB Output is correct
5 Correct 36 ms 56696 KB Output is correct
6 Correct 36 ms 56828 KB Output is correct
7 Correct 43 ms 56696 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 63324 KB Output is correct
2 Correct 308 ms 66772 KB Output is correct
3 Correct 498 ms 68568 KB Output is correct
4 Correct 1484 ms 158204 KB Output is correct
5 Correct 1575 ms 174080 KB Output is correct
6 Correct 1254 ms 144120 KB Output is correct
7 Correct 2132 ms 225508 KB Output is correct
8 Correct 1705 ms 213736 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 56832 KB Output is correct
2 Correct 38 ms 56696 KB Output is correct
3 Correct 38 ms 57080 KB Output is correct
4 Correct 37 ms 57216 KB Output is correct
5 Correct 680 ms 79608 KB Output is correct
6 Correct 1266 ms 139880 KB Output is correct
7 Correct 1780 ms 207572 KB Output is correct
8 Correct 2231 ms 308104 KB Output is correct
9 Correct 275 ms 67160 KB Output is correct
10 Correct 308 ms 67264 KB Output is correct
11 Correct 334 ms 70344 KB Output is correct
12 Correct 2721 ms 319088 KB Output is correct
13 Correct 2220 ms 308248 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 57208 KB Output is correct
2 Correct 38 ms 57080 KB Output is correct
3 Correct 39 ms 56960 KB Output is correct
4 Correct 35 ms 56704 KB Output is correct
5 Correct 2607 ms 309344 KB Output is correct
6 Correct 1925 ms 231836 KB Output is correct
7 Correct 1340 ms 158968 KB Output is correct
8 Correct 613 ms 72908 KB Output is correct
9 Correct 785 ms 121316 KB Output is correct
10 Correct 367 ms 64996 KB Output is correct
11 Correct 781 ms 121504 KB Output is correct
12 Correct 374 ms 65120 KB Output is correct
13 Correct 787 ms 121312 KB Output is correct
14 Correct 365 ms 64996 KB Output is correct
15 Correct 2670 ms 318696 KB Output is correct
16 Correct 2224 ms 308192 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 56704 KB Output is correct
2 Correct 37 ms 56704 KB Output is correct
3 Correct 35 ms 56696 KB Output is correct
4 Correct 35 ms 56696 KB Output is correct
5 Correct 36 ms 56696 KB Output is correct
6 Correct 36 ms 56828 KB Output is correct
7 Correct 43 ms 56696 KB Output is correct
8 Correct 257 ms 63324 KB Output is correct
9 Correct 308 ms 66772 KB Output is correct
10 Correct 498 ms 68568 KB Output is correct
11 Correct 1484 ms 158204 KB Output is correct
12 Correct 1575 ms 174080 KB Output is correct
13 Correct 1254 ms 144120 KB Output is correct
14 Correct 2132 ms 225508 KB Output is correct
15 Correct 1705 ms 213736 KB Output is correct
16 Correct 36 ms 56832 KB Output is correct
17 Correct 38 ms 56696 KB Output is correct
18 Correct 38 ms 57080 KB Output is correct
19 Correct 37 ms 57216 KB Output is correct
20 Correct 680 ms 79608 KB Output is correct
21 Correct 1266 ms 139880 KB Output is correct
22 Correct 1780 ms 207572 KB Output is correct
23 Correct 2231 ms 308104 KB Output is correct
24 Correct 275 ms 67160 KB Output is correct
25 Correct 308 ms 67264 KB Output is correct
26 Correct 334 ms 70344 KB Output is correct
27 Correct 2721 ms 319088 KB Output is correct
28 Correct 2220 ms 308248 KB Output is correct
29 Correct 37 ms 57208 KB Output is correct
30 Correct 38 ms 57080 KB Output is correct
31 Correct 39 ms 56960 KB Output is correct
32 Correct 35 ms 56704 KB Output is correct
33 Correct 2607 ms 309344 KB Output is correct
34 Correct 1925 ms 231836 KB Output is correct
35 Correct 1340 ms 158968 KB Output is correct
36 Correct 613 ms 72908 KB Output is correct
37 Correct 785 ms 121316 KB Output is correct
38 Correct 367 ms 64996 KB Output is correct
39 Correct 781 ms 121504 KB Output is correct
40 Correct 374 ms 65120 KB Output is correct
41 Correct 787 ms 121312 KB Output is correct
42 Correct 365 ms 64996 KB Output is correct
43 Correct 2670 ms 318696 KB Output is correct
44 Correct 2224 ms 308192 KB Output is correct
45 Correct 149 ms 62032 KB Output is correct
46 Correct 313 ms 64520 KB Output is correct
47 Correct 961 ms 136792 KB Output is correct
48 Correct 1635 ms 186104 KB Output is correct
49 Correct 329 ms 68424 KB Output is correct
50 Correct 317 ms 67788 KB Output is correct
51 Correct 372 ms 70864 KB Output is correct
52 Correct 705 ms 155980 KB Output is correct
53 Correct 714 ms 155980 KB Output is correct
54 Correct 712 ms 155980 KB Output is correct