Submission #278901

#	Time	Username	Problem	Language	Result	Execution time	Memory
278901		limabeans	가로등 (APIO19_street_lamps)	C++17	20 / 100	1 ms	512 KiB

street_lamps

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e6 + 5;

struct bit {
    int n, m;
    vector<vector<int>> t;
    void init(int n, int m) {
	n += 10; m += 10;
	this->n=n;
	this->m=m;

	t.resize(n, vector<int>(m, 0));
    }

    void upd(int r1, int c1, int dx) {
	for (int r=r1; r<n; r+=r&-r) {
	    for (int c=c1; c<m; c+=c&-c) {
		t[r][c] += dx;
	    }
	}
    }

    void set(int r1, int c1, int val) {
	int old = qry(r1,c1,r1,c1);
	upd(r1,c1,val-old);
    }

    int get(int r1, int c1) {
	int res = 0;
	for (int r=r1; r; r-=r&-r) {
	    for (int c=c1; c; c-=c&-c) {
		res += t[r][c];
	    }
	}
	return res;
    }

    int qry(int r1, int c1, int r2, int c2) {
	return get(r2,c2)-get(r1-1,c2)-get(r2,c1-1)+get(r1-1,c1-1);
    }
};



int n, q;
bit t;
string s;

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

    cin>>n>>q;
    assert(n<=100 && q<=100); // Subtask 1

    cin>>s;
    s="*"+s;

    auto work = [&]() {
	for (int i=1; i<=n; ) {
	    if (s[i]=='0') {
		i++;
		continue;
	    }
	    int j=i;
	    while (j<=n && s[j]=='1') {
		j++;
	    }
	    t.upd(i,j-1,1);
	    i=j;
	}
    };

    t.init(n+10,n+10);

    //work();

    // Each event takes place at the end of the hour.
    while (q--) {
	work();
	string op;
	cin>>op;

	if (op=="toggle") {
	    int idx;
	    cin>>idx;
	    s[idx] ^= 1;
	}
	if (op=="query") {
	    int l, r;
	    cin>>l>>r;
	    r--;
	    // Rectangle
	    // ...............N
	    // .             .
	    // .             .
	    // .   (s,e)     . 
	    // .             . 
	    // ...............R
	    //
	    //
	    //
	    // 1             L
	    // (s,e): s<=L and R<=e, so (s,e) will cover our trip from L to R.
	    int res = t.qry(1,r,l,n);
	    cout<<res<<"\n";
	}
    }


    
    
    return 0;
}

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