Submission #1107099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107099		InvMOD	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	1008 ms	100080 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define gcd __gcd
#define sz(v) (int) v.size()
#define pb push_back
#define pi pair<int,int>
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define dbg(x) "[" #x " = " << (x) << "]"
///#define int long long

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;}

const int N = 3e5+5;
const ll MOD = 1e9+7;
const ll INF = 1e18;

// Nhớ viết Note lại nha InvMOD :3c


namespace Subtask1{
    bool check(int n, int q){return n <= 100 && q <= 100;}

    bool good(string& state, int l, int r){
        // :) troll troll bulb i can only light up i and i+1
        for(int i = l; i < r; i++)
            if(state[i] == '0') return false;
        return true;
    }

    void process(int n, int q)
    {
        string s; cin >> s;
        s = " " + s;

        vector<string> state(q+1);
        state[0] = s;

        for(int i = 1; i <= q; i++){
            string op; cin >> op;
            if(op == "toggle"){
                int idx; cin >> idx; // change type
                s[idx] = char((int(s[idx] - '0')^1) + '0');
                state[i] = s;
            }
            else{
                int l,r; cin >> l >> r;
                state[i] = s;

                int answer = 0;
                for(int j = 0; j < i; j++){
                    answer = answer + good(state[j], l, r);
                }

                cout << answer <<"\n";
            }
        }
    }
}

namespace Subtask5{
    /*
        Update need l, r, value
        Query need l, r, and id
    */
    struct Query{
        int x, y, value;
        Query(int x = 0, int y = 0, int value = 0): x(x), y(y), value(value) {}
        bool operator < (const Query& q) const{
            return x < q.x;
        }
    };

    int n, q, answer[N], bit[N];
    vector<Query> Q[N];

    void update(int p, int val){
        for(; p <= n+1; p += (p&(-p))) bit[p] += val;
        return;
    }

    int get(int p){
        int res = 0;
        for(; p; p -= (p&(-p))) res += bit[p];
        return res;
    }

    void Dnc(int l, int r){
        if(l >= r){
            return;
        }
        else{
            int m = l+r>>1;

            vector<Query> Que, Upd;

            // Get all Upd and Que
            for(int i = l; i <= m; i++){
                if(sz(Q[i]) > 1){
                    for(int j = 0; j < sz(Q[i]); j++){
                        Upd.push_back(Q[i][j]);
                    }
                }
            }
            for(int i = m+1; i <= r; i++){
                if(sz(Q[i]) == 1){
                    Que.push_back(Q[i][0]);
                }
            }

            sort(all(Que)), sort(all(Upd));

            stack<int> save_Upd;

            int pointer = 0;
            for(Query& cur_q : Que){
                while(pointer < sz(Upd) && Upd[pointer].x <= cur_q.x){
                    update(Upd[pointer].y, Upd[pointer].value);
                    save_Upd.push(pointer++);
                }

                answer[cur_q.value] += get(cur_q.y);
            }

            while(!save_Upd.empty()){
                int id = save_Upd.top();
                update(Upd[id].y, -Upd[id].value);
                save_Upd.pop();
            }

            Dnc(l, m), Dnc(m+1, r);
        }
        return;
    }

    void process(int _cntQ)
    {
        string s; cin >> s;
        n = sz(s); s = " " + s + " ";

        q = _cntQ;

        // Prepare: Add all good segment

        multiset<pair<int,int>> good;

        int ptr = 1;
        while(ptr <= n){
            if(s[ptr] == '0'){
                ptr++;
            }
            else{
                int l = ptr;
                while(ptr < n && s[ptr+1] == '1') ++ptr;

                // Add all segment with start >= l && start <= r and end >= l && end <= r

                Q[0].push_back(Query(l, l  , +q));
                Q[0].push_back(Query(l, ptr+1, -q));
                good.insert(make_pair(l,ptr++));
            }
        }

        for(int i = 1; i <= q; i++){
            string type; cin >> type;

            if(type == "toggle"){
                int x; cin >> x;

                if(!good.size()){
                    good.insert(make_pair(x, x));
                    Q[i].push_back(Query(x, x  , +(q-i)));
                    Q[i].push_back(Query(x, x+1, -(q-i)));
                    s[x] = '1';
                    continue;
                }

                if(s[x] == '0'){
                    //turn on, there is no segment in good that is [x, x]
                    s[x] = '1';

                    bool can_join = false;
                    int nwL = x, nwR = x;

                    if(s[x-1] == '1'){
                        can_join = true;
                        auto left_itr = good.lower_bound(make_pair(x, -1)); --left_itr;
                        int l = (*left_itr).first, r = (*left_itr).second;
                        nwL = min(nwL, l), nwR = max(nwR, r);

                        // Reverse update
                        Q[i].push_back(Query(l, l  , -(q-i)));
                        Q[i].push_back(Query(l, r+1, +(q-i)));
                        good.erase(left_itr);
                    }

                    if(s[x+1] == '1'){
                        can_join = true;
                        auto right_itr = good.lower_bound(make_pair(x, -1));
                        int l = (*right_itr).first, r = (*right_itr).second;
                        nwL = min(nwL, l), nwR = max(nwR, r);

                        // Reverse update
                        Q[i].push_back(Query(l, l  , -(q-i)));
                        Q[i].push_back(Query(l, r+1, +(q-i)));
                        good.erase(right_itr);
                    }

                    // Insert New Segment
                    if(!can_join){
                        Q[i].push_back(Query(x, x  , +(q-i)));
                        Q[i].push_back(Query(x, x+1, -(q-i)));
                        good.insert(make_pair(x, x));
                    }
                    else{
                        Q[i].push_back(Query(nwL, nwL  , +(q-i)));
                        Q[i].push_back(Query(nwL, nwR+1, -(q-i)));
                        good.insert(make_pair(nwL, nwR));
                    }
                }
                else{ // turn off
                    s[x] = '0';

                    auto itr = good.upper_bound(make_pair(x, n+1)); --itr;

                    int l = (*itr).first, r = (*itr).second;

                    Q[i].push_back(Query(l, l  , -(q-i)));
                    Q[i].push_back(Query(l, r+1, +(q-i)));

                    if(s[x-1] == '1'){
                        // Reupdate
                        Q[i].push_back(Query(l, l, +(q-i)));
                        Q[i].push_back(Query(l, x, -(q-i)));
                        good.insert(make_pair(l, x-1));
                    }

                    if(s[x+1] == '1'){
                        // Reupdate
                        Q[i].push_back(Query(x+1, x+1, +(q-i)));
                        Q[i].push_back(Query(x+1, r+1, -(q-i)));
                        good.insert(make_pair(x+1, r));
                    }

                    good.erase(itr);
                }
            }
            else{
                int l,r; cin >> l >> r;
                if(l == r){
                    answer[i] = i;
                    continue;
                }

                Q[i].push_back(Query(l, r-1, i));

                if(good.size()){
                    auto itr = good.upper_bound(make_pair(l, n+1)); --itr;

                    if(((*itr).first <= l && r-1 <= (*itr).second)){
                        answer[i] += -(q-i);
                    }
                }
            }
        }

        Dnc(0, q);
        for(int i = 1; i <= q; i++){
            if(sz(Q[i]) <= 1){
                cout << answer[i] <<"\n";
            }
        }
        return;
    }
}

void solve()
{
    int n,q; cin >> n >> q;

    Subtask5::process(q);
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP","r",stdin);
        freopen(name".OUT","w",stdout);
    }

    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'void Subtask5::Dnc(int, int)':
street_lamps.cpp:102:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |             int m = l+r>>1;
      |                     ~^~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:301:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  301 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:302:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  302 |         freopen(name".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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