Submission #953050

#	Time	Username	Problem	Language	Result	Execution time	Memory
953050		Vladth11	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	5032 ms	66688 KiB

street_lamps

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;

const ll NMAX = 300001;
const int INF = 1e9;
const ll nrbits = 20;
const ll MOD = 998244353;

int n;

class AINT{
public:
    struct Node{
        int sum, st, dr;
    };
    vector <Node> aint;
    void update(int node, int st, int dr, int a, int b, int val){
        debug("AICI");
        debug(node);
        if(!aint.size()){
            aint.push_back({0, -1, -1});
        }
        if(a <= st && dr <= b){
            aint[node].sum += val;
            return;
        }
        int mid = (st + dr) / 2;
        if(a <= mid){
            if(aint[node].st == -1){
                aint[node].st = aint.size();
                aint.push_back({0, -1, -1});
            }
            update(aint[node].st, st, mid, a, b, val);
        }
        if(b > mid){
            if(aint[node].dr == -1){
                aint[node].dr = aint.size();
                aint.push_back({0, -1, -1});
            }
            update(aint[node].dr, mid + 1, dr, a, b, val);
        }
    }
    int query(int node, int st, int dr, int a){
        if(node == -1 || !aint.size()){
            return 0;
        }
        int aici = aint[node].sum;
        if(st == dr)
            return aici;
        int mid = (st + dr) / 2;
        if(a <= mid){
            return aici + query(aint[node].st, st, mid, a);
        }
        return aici + query(aint[node].dr, mid + 1, dr, a);
    }
}stt[NMAX * 4];

void update(int node, int st, int dr, int x1, int x2, int y1, int y2, int val){
    if(x2 < x1) return;
    if(y2 < y1) return;
    if(x1 <= st && dr <= x2){
        stt[node].update(0, 1, n, y1, y2, val);
        return;
    }
    int mid = (st + dr) / 2;
    if(x1 <= mid)
        update(node * 2, st, mid, x1, x2, y1, y2, val);
    if(x2 > mid)
        update(node * 2 + 1, mid + 1, dr, x1, x2, y1, y2, val);
}

int query(int node, int st, int dr, int x, int y){
    int aici = stt[node].query(0, 1, n, y);
    if(st == dr){
        return aici;
    }
    int mid = (st + dr) / 2;
    if(x <= mid)
        return aici + query(node * 2, st, mid, x, y);
    return aici + query(node * 2 + 1, mid + 1, dr, x, y);
}

int a[NMAX];
string s[NMAX];
int qa[NMAX];
int qb[NMAX];

int aib[NMAX * 4];

void upd(int node, int val){
    for(; node <= n; node += node&(-node))
        aib[node] += val;
}

int qry(int node){
    int val = 0;
    for(; node; node -= node&(-node))
        val += aib[node];
    return val;
}

signed main() {
#ifdef HOME
    ifstream cin(".in");
    ofstream cout(".out");
#endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int i, q;
    cin >> n >> q;
    for(i = 1; i <= n; i++){
        char c;
        cin >> c;
        a[i] = c - '0';
        upd(i, a[i]);
    }
    for(i = 1; i <= q; i++){
        cin >> s[i];
        cin >> qa[i];
        if(s[i][0] == 'q'){
            cin >> qb[i];
            qb[i]--;
            cout << query(1, 1, n, qa[i], qb[i]) + i * ((qry(qb[i]) - qry(qa[i] - 1)) == (qb[i] - qa[i] + 1)) << "\n";
        }else{
            if(a[qa[i]] == 1){
                int r = 0, pas = (1 << nrbits);
                while(pas){
                    if(r + pas <= qa[i] && qry(qa[i]) - qry(r + pas - 1) != (qa[i] - (r + pas) + 1))
                        r += pas;
                    pas /= 2;
                }
                r++;
                int st = r;
                r = qa[i], pas = (1 << nrbits);
                while(pas){
                    if(r + pas <= n && qry(r + pas) - qry(qa[i] - 1) == ((r + pas) - qa[i] + 1))
                        r += pas;
                    pas /= 2;
                }
                int dr = r;
                update(1, 1, n, st, qa[i], qa[i], dr, i);
            }else{
                int r = 0, pas = (1 << nrbits);
                while(pas){
                    if(r + pas < qa[i] && qry(qa[i]) - qry(r + pas - 1) != (qa[i] - (r + pas)))
                        r += pas;
                    pas /= 2;
                }
                r++;
                int st = r;
                r = qa[i], pas = (1 << nrbits);
                while(pas){
                    if(r + pas <= n && qry(r + pas) - qry(qa[i] - 1) == ((r + pas) - qa[i]))
                        r += pas;
                    pas /= 2;
                }
                int dr = r;
                update(1, 1, n, st, qa[i], qa[i], dr, -i);
            }
            upd(qa[i], -a[qa[i]]);
            a[qa[i]] ^= 1;
            upd(qa[i], a[qa[i]]);
        }
    }
    return 0;
}

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