Submission #1265535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265535		CrabCNH	Street Lamps (APIO19_street_lamps)	C++20	100 / 100	1312 ms	117256 KiB

street_lamps

#include <bits/stdc++.h>

#define task     "BriantheCrab"

#define int    long long
#define pii    pair <int, int>
#define fi     first
#define se     second
#define szf    sizeof
#define sz(s)  (int)((s).size())
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using namespace std;

template <class T> void minimize (T &t, T f) {if (t > f) t = f;}
template <class T> void maximize (T &t, T f) {if (t < f) t = f;}

const int maxN = 5e5 + 5;
const int inf = 1e18 + 7;
const int mod = 1e9 + 7;

// khong tu code thi khong kha len duoc dau
// biet sol roi thi tu lam not di

struct query {
    int t, x, y, val; // 0: upd, 1 : sumadd, -1 : sumdel
};

bool cmp (query A, query B) {
    return A.t < B.t;
}

bool cmpY (query A, query B) {
    return A.y > B.y;
}

int n;
int a[maxN];
int lst[maxN], res[maxN];
vector <query> ok;
vector <int> posQ;
int Z;

struct Fenwick {
    int bit[maxN];
    
    inline void reset () {
        for (int id = 1; id < maxN; id ++) {
            bit[id] = 0;
        }
    }
    
    inline void upd (int id, int val) {
        for (; id < maxN; id += id & (-id)) {
            bit[id] += val;
        }
    }
    
    inline int getP (int id) {
        int res = 0;
        for (; id; id -= id & (-id)) {
            res += bit[id];
        }
        return res;
    }
    
    inline int get (int l, int r) {
        return getP (r) - getP (l - 1);
    }
    
    inline int find (int k) {
        int l = 1, r = n + 2, res = n + 2;
        while (true) {
            if (l > r) {
                break;
            }
            int mid = (l + r) >> 1;
            if (getP (mid) >= k) {
                res = mid;
                r = mid - 1;
            }
            else {
                l = mid + 1;
            }
        }
        return res;
    }
};

Fenwick Tz, T1, T2;

void cdq (int l, int r) {
    if (l == r) {
        return;
    }
    //cout << l << ' ' << r << '\n';
    int m = (l + r) >> 1;
    cdq (l, m), cdq (m + 1, r);
    vector <query> upd, que, reset;
    for (int i = l; i <= m; i ++) {
        if (ok[i].val != 0) {
            upd.push_back (ok[i]);
        }
    }
    for (int i = m + 1; i <= r; i ++) {
        if (ok[i].val == 0) {
            que.push_back (ok[i]);
        } 
    }
    sort (all (upd), cmpY);
    sort (all (que), cmpY);
    int lp = 0, rp = 0;
    while (lp < sz (upd) && rp < sz (que)) {
        if (upd[lp].y >= que[rp].y) {
            T1.upd (upd[lp].x + 1, upd[lp].val);
            T2.upd (upd[lp].x + 1, upd[lp].val * upd[lp].t);
            reset.push_back (upd[lp ++]);
        }
        else {
            res[que[rp].t] += que[rp].t * T1.getP (que[rp].x + 1) - T2.getP (que[rp].x + 1);
            rp ++;
        }
    }
    while (rp < sz (que)) {
        res[que[rp].t] += que[rp].t * T1.getP (que[rp].x + 1) - T2.getP (que[rp].x + 1);
        rp ++;
    }
    for (auto it : reset) {
        T1.upd (it.x + 1, - it.val);
        T2.upd (it.x + 1, - it.val * it.t);
    }
}

void solve () {
    int q;
    cin >> n >> q;
    for (int i = 1; i <= n; i ++) {
        char x;
        cin >> x;
        a[i] = (x == '1'); 
    }
    Tz.upd (0 + 1, 1);
    Tz.upd (n + 1 + 1, 1);
    for (int i = 1; i <= n; i ++) {
        if (a[i] == 0) {
            Tz.upd (i + 1, 1);
        }
    }
    int lim = Tz.getP (n + 1 + 1);
    int lst = Tz.find (1) - 1;
    for (int k = 2; k <= lim; k ++) {
        int cur = Tz.find (k) - 1;
        ok.push_back ({0, lst, cur, 1});
        lst = cur;
    }
    for (int i = 1; i <= q; i ++) {
        string t;
        cin >> t;
        if (t == "query") {
            int x, y;
            cin >> x >> y;
            posQ.push_back (i);
            ok.push_back ({i, x - 1, y, 0});
        }
        else {
            int x;
            cin >> x;
            if (a[x] == 0) {
                int c = Tz.getP (x + 1);
                int l = Tz.find (c - 1) - 1;
                int r = Tz.find (c + 1) - 1;
                //cout << c << ' ' << l << ' ' << r << '\n';
                ok.push_back ({i, l, x, -1});
                ok.push_back ({i, x, r, -1});
                ok.push_back ({i, l, r, 1});
                Tz.upd (x + 1, -1);
                a[x] = 1;
            }
            else {
                int c = Tz.getP (x + 1);
                int l = Tz.find (c) - 1;
                int r = Tz.find (c + 1) - 1;
                //cout << c << ' ' << l << ' ' << r << '\n';
                ok.push_back ({i, l, r, -1});
                ok.push_back ({i, l, x, 1});
                ok.push_back ({i, x, r, 1});
                Tz.upd (x + 1, 1);
                a[x] = 0;
            }
        }
    }
    sort (all (ok), cmp);
    cdq (0, sz (ok) - 1);
    for (auto it : posQ) {
        cout << res[it] << '\n';
    }
    return;
}

signed main () {
    cin.tie (nullptr) -> sync_with_stdio (false);
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    int t = 1;
    //cin >> t;
    while (t --) {
        solve ();
    } 
    return 0;
}
// thfv

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:207:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  207 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:208:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  208 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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