oj.uz

Submission #1107098

# Submission time Handle Problem Language Result Execution time Memory
1107098 2024-10-31T16:23:40 Z InvMOD Street Lamps (APIO19_street_lamps) C++14
100 / 100
 1044 ms 99564 KB 
#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;



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;
        }
        void check(){
            cout << x <<" " << y <<" " << value <<"\n";
        }
    };

    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);
                //cout << cur_q.value <<" " << dbg(cur_q.x) <<" " << dbg(cur_q.y) <<" " << get(cur_q.y) <<"\n";
            }

            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);
                    }
                }
            }
        }

        /*
        for(int i = 0; i <= q; i++){
            if(sz(Q[i]) > 1){
                cout << "Check Query: " << i <<"\n";
                for(Query cur_q : Q[i]) cur_q.check();
                cout <<"\n";
            }
        }
        */

        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);

    //if(Subtask1::check(n, q)) Subtask1::process(n, q), exit(0);
}

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

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8784 KB Output is correct
2 Correct 2 ms 8832 KB Output is correct
3 Correct 2 ms 8952 KB Output is correct
4 Correct 3 ms 8784 KB Output is correct
5 Correct 3 ms 8784 KB Output is correct
6 Correct 2 ms 8784 KB Output is correct
7 Correct 3 ms 8784 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 40204 KB Output is correct
2 Correct 511 ms 40124 KB Output is correct
3 Correct 549 ms 39868 KB Output is correct
4 Correct 921 ms 89072 KB Output is correct
5 Correct 900 ms 93176 KB Output is correct
6 Correct 699 ms 97420 KB Output is correct
7 Correct 245 ms 30340 KB Output is correct
8 Correct 242 ms 30220 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8784 KB Output is correct
2 Correct 3 ms 9040 KB Output is correct
3 Correct 3 ms 9040 KB Output is correct
4 Correct 2 ms 8844 KB Output is correct
5 Correct 795 ms 55404 KB Output is correct
6 Correct 1044 ms 84284 KB Output is correct
7 Correct 872 ms 95864 KB Output is correct
8 Correct 273 ms 30408 KB Output is correct
9 Correct 116 ms 23296 KB Output is correct
10 Correct 135 ms 25824 KB Output is correct
11 Correct 133 ms 25788 KB Output is correct
12 Correct 270 ms 30596 KB Output is correct
13 Correct 260 ms 30288 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8784 KB Output is correct
2 Correct 3 ms 9040 KB Output is correct
3 Correct 4 ms 9040 KB Output is correct
4 Correct 5 ms 9040 KB Output is correct
5 Correct 506 ms 77216 KB Output is correct
6 Correct 608 ms 95668 KB Output is correct
7 Correct 703 ms 98316 KB Output is correct
8 Correct 789 ms 99564 KB Output is correct
9 Correct 428 ms 53468 KB Output is correct
10 Correct 462 ms 51376 KB Output is correct
11 Correct 435 ms 51216 KB Output is correct
12 Correct 439 ms 51628 KB Output is correct
13 Correct 430 ms 52648 KB Output is correct
14 Correct 429 ms 51100 KB Output is correct
15 Correct 259 ms 30340 KB Output is correct
16 Correct 257 ms 30340 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8784 KB Output is correct
2 Correct 2 ms 8832 KB Output is correct
3 Correct 2 ms 8952 KB Output is correct
4 Correct 3 ms 8784 KB Output is correct
5 Correct 3 ms 8784 KB Output is correct
6 Correct 2 ms 8784 KB Output is correct
7 Correct 3 ms 8784 KB Output is correct
8 Correct 459 ms 40204 KB Output is correct
9 Correct 511 ms 40124 KB Output is correct
10 Correct 549 ms 39868 KB Output is correct
11 Correct 921 ms 89072 KB Output is correct
12 Correct 900 ms 93176 KB Output is correct
13 Correct 699 ms 97420 KB Output is correct
14 Correct 245 ms 30340 KB Output is correct
15 Correct 242 ms 30220 KB Output is correct
16 Correct 3 ms 8784 KB Output is correct
17 Correct 3 ms 9040 KB Output is correct
18 Correct 3 ms 9040 KB Output is correct
19 Correct 2 ms 8844 KB Output is correct
20 Correct 795 ms 55404 KB Output is correct
21 Correct 1044 ms 84284 KB Output is correct
22 Correct 872 ms 95864 KB Output is correct
23 Correct 273 ms 30408 KB Output is correct
24 Correct 116 ms 23296 KB Output is correct
25 Correct 135 ms 25824 KB Output is correct
26 Correct 133 ms 25788 KB Output is correct
27 Correct 270 ms 30596 KB Output is correct
28 Correct 260 ms 30288 KB Output is correct
29 Correct 3 ms 8784 KB Output is correct
30 Correct 3 ms 9040 KB Output is correct
31 Correct 4 ms 9040 KB Output is correct
32 Correct 5 ms 9040 KB Output is correct
33 Correct 506 ms 77216 KB Output is correct
34 Correct 608 ms 95668 KB Output is correct
35 Correct 703 ms 98316 KB Output is correct
36 Correct 789 ms 99564 KB Output is correct
37 Correct 428 ms 53468 KB Output is correct
38 Correct 462 ms 51376 KB Output is correct
39 Correct 435 ms 51216 KB Output is correct
40 Correct 439 ms 51628 KB Output is correct
41 Correct 430 ms 52648 KB Output is correct
42 Correct 429 ms 51100 KB Output is correct
43 Correct 259 ms 30340 KB Output is correct
44 Correct 257 ms 30340 KB Output is correct
45 Correct 233 ms 27064 KB Output is correct
46 Correct 283 ms 27968 KB Output is correct
47 Correct 467 ms 42792 KB Output is correct
48 Correct 874 ms 92076 KB Output is correct
49 Correct 157 ms 27396 KB Output is correct
50 Correct 146 ms 27608 KB Output is correct
51 Correct 144 ms 27580 KB Output is correct
52 Correct 160 ms 27988 KB Output is correct
53 Correct 147 ms 28096 KB Output is correct
54 Correct 139 ms 27992 KB Output is correct