Submission #277011

#	Time	Username	Problem	Language	Result	Execution time	Memory
277011		limabeans	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	400 ms	18148 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;
const int inf = 1e9;

template<typename T> struct segtree {
    
    T merge(T x, T y) {
	return max(x, y);
    }
    int n;
    vector<ll> t;
    void init(int n) {
	n += 10;
	this->n = n;
	t.resize(n*4);
    }

    void upd(int v, int tl, int tr, int i, T val) {
	if (tl == tr) {
	    t[v] = val;
	} else {
	    int tm = (tl+tr)/2;
	    if (i<=tm) {
		upd(2*v,tl,tm,i,val);
	    } else {
		upd(2*v+1,tm+1,tr,i,val);
	    }
	    t[v] = merge(t[2*v], t[2*v+1]);
	}
    }

    T qry(int v, int tl, int tr, int l, int r) {
	if (l>tr || r<tl) {
	    return -inf;
	}
	if (l <= tl && tr <= r) {
	    return t[v];
	}
	int tm = (tl+tr)/2;
	return merge(qry(2*v,tl,tm,l,r), qry(2*v+1,tm+1,tr,l,r));
    }
};

int n, q;
string s;
segtree<int> tree;


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

    cin>>n>>q;
    tree.init(n+10);
    for (int i=1; i<=n; i++) {
	tree.upd(1,1,n,i,inf);
    }

    cin>>s;
    s = "*" + s;
    for (int i=1; i<=n; i++) {
	if (s[i] == '1') {
	    tree.upd(1,1,n,i,0);
	}
    }

    // Solving task3, assume all toggles turn things on
    for (int time=1; time<=q; time++) {
	string type;
	cin>>type;
	if (type[0] == 't') {
	    int i;
	    cin>>i;
	    assert(s[i]=='0');
	    s[i]='1';
	    tree.upd(1,1,n,i,time);
	}

	if (type[0] == 'q') {
	    int a,b;
	    cin>>a>>b;
	    int latest = tree.qry(1,1,n,a,b-1);
	    int ans = time-latest;
	    if (latest == inf) ans = 0;
	    cout<<ans<<"\n";
	}
    }
    
    
    return 0;
}

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