Submission #706080

#	Time	Username	Problem	Language	Result	Execution time	Memory
706080		fatemetmhr	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	2758 ms	251176 KiB

street_lamps

// ~ Be Name Khoda ~

#include <bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  3e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  1e18;

struct segment_tree{

    vector <int> lazy;
    int n;

    inline void add(int l, int r, int lq, int rq, int val, int v){
        if(rq <= l || r <= lq)
            return;
        if(lq <= l && r <= rq){
            lazy[v] += val;
            return;
        }
        int mid = (l + r) >> 1;
        add(l, mid, lq, rq, val, v * 2);
        add(mid, r, lq, rq, val, v * 2 + 1);
    }

    inline int get(int l, int r, int id, int v){
        if(r - l == 1)
            return lazy[v];
        int mid = (l + r) >> 1;
        if(id < mid)
            return get(l, mid, id, v * 2) + lazy[v];
        return get(mid, r, id, v * 2 + 1) + lazy[v];
    }

} seg[maxnt];

set <int> av;
string ty[maxn5];
int x[maxn5], y[maxn5];
vector <int> have[maxnt], req[maxn5];

void build(int l, int r, int v){
    if(r - l == 1){
        for(auto u : req[l])
            have[v].pb(u);
        sort(all(have[v]));
    }
    else{
        int mid = (l + r) >> 1;
        build(l, mid, v * 2);
        build(mid, r, v * 2 + 1);
        int pt1 = 0, pt2 = 0;
        while(pt1 < have[v * 2].size() || pt2 < have[v * 2 + 1].size()){
            if(pt1 < have[v * 2].size() && (pt2 == have[v * 2 + 1].size() || have[v * 2][pt1] < have[v * 2 + 1][pt2]))
                have[v].pb(have[v * 2][pt1++]);
            else
                have[v].pb(have[v * 2 + 1][pt2++]);
        }
    }
    have[v].resize(unique(all(have[v])) - have[v].begin());
    seg[v].n = have[v].size();
    seg[v].lazy.resize((seg[v].n << 2) + 5);
}

void add(int l, int r, int lq, int rq, int lq2, int rq2, int val, int v){
    if(rq <= l || r <= lq)
        return;
    if(lq <= l && r <= rq){
        int ptl = lower_bound(all(have[v]), lq2) - have[v].begin();
        int ptr = lower_bound(all(have[v]), rq2) - have[v].begin();
        if(ptl < ptr)
            seg[v].add(0, seg[v].n, ptl, ptr, val, 1);
        return;
    }
    int mid = (l + r) >> 1;
    add(l, mid, lq, rq, lq2, rq2, val, v * 2);
    add(mid, r, lq, rq, lq2, rq2, val, v * 2 + 1);
}

int get(int l, int r, int id1, int id2, int v){
    int pt = lower_bound(all(have[v]), id2) - have[v].begin();
    int ret = 0;
    if(pt < have[v].size() && have[v][pt] == id2)
        ret += seg[v].get(0, seg[v].n, pt, 1);
    if(r - l > 1){
        int mid = (l + r) >> 1;
        if(id1 < mid)
            ret += get(l, mid, id1, id2, v * 2);
        else
            ret += get(mid, r, id1, id2, v * 2 + 1);
    }
    return ret;
}

inline bool is_ok(int l, int r){
    auto it = av.lower_bound(l);
    if((*it) <= r)
        return false;
    return true;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n, q; cin >> n >> q;
    string s; cin >> s;
    for(int i = 0; i < q; i++){
        cin >> ty[i] >> x[i];
        x[i]--;
        if(ty[i] == "query"){
            cin >> y[i];
            y[i] -= 2;
            req[x[i]].pb(y[i]);
        }
    }
    build(0, n, 1);
    int last = 0;
    for(int i = 0; i < n; i++) if(s[i] == '0'){
        av.insert(i);
        if(last < i)
            add(0, n, last, i, last, i, q, 1);
        last = i + 1;
    }
    if(last < n)
        add(0, n, last, n, last, n, q, 1);
    av.insert(-1);
    av.insert(n);
    for(int i = 0; i < q; i++){
        if(ty[i] == "query")
            cout << get(0, n, x[i], y[i], 1) + (is_ok(x[i], y[i]) ? -1 : 0) * (q - i - 1) << '\n';
        else{
            bool cur = av.find(x[i]) == av.end();
            av.erase(x[i]);
            auto it = av.lower_bound(x[i]);
            int r = *it;
            it--;
            int l = *it;
            add(0, n, l + 1, x[i] + 1, x[i], r, (cur ? -1 : 1) * (q - i - 1), 1);
            if(cur)
                av.insert(x[i]);
        }
    }
}

Compilation message (stderr)

street_lamps.cpp: In function 'void build(int, int, int)':
street_lamps.cpp:69:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         while(pt1 < have[v * 2].size() || pt2 < have[v * 2 + 1].size()){
      |               ~~~~^~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:69:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         while(pt1 < have[v * 2].size() || pt2 < have[v * 2 + 1].size()){
      |                                           ~~~~^~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:70:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |             if(pt1 < have[v * 2].size() && (pt2 == have[v * 2 + 1].size() || have[v * 2][pt1] < have[v * 2 + 1][pt2]))
      |                ~~~~^~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:70:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |             if(pt1 < have[v * 2].size() && (pt2 == have[v * 2 + 1].size() || have[v * 2][pt1] < have[v * 2 + 1][pt2]))
      |                                             ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'int get(int, int, int, int, int)':
street_lamps.cpp:99:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     if(pt < have[v].size() && have[v][pt] == id2)
      |        ~~~^~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20