oj.uz

Submission #277011

# Submission time Handle Problem Language Result Execution time Memory
277011 2020-08-21T00:56:22 Z limabeans Street Lamps (APIO19_street_lamps) C++17
20 / 100
 400 ms 18148 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 416 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 221 ms 14436 KB Output is correct
6 Correct 287 ms 15204 KB Output is correct
7 Correct 324 ms 15844 KB Output is correct
8 Correct 394 ms 18148 KB Output is correct
9 Correct 103 ms 4136 KB Output is correct
10 Correct 108 ms 4344 KB Output is correct
11 Correct 110 ms 4516 KB Output is correct
12 Correct 343 ms 17016 KB Output is correct
13 Correct 400 ms 18124 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -