oj.uz

Submission #392603

# Submission time Handle Problem Language Result Execution time Memory
392603 2021-04-21T11:01:58 Z BorisBarca Street Lamps (APIO19_street_lamps) C++14
60 / 100
 310 ms 19680 KB 
/*
$$$$$$$\                      $$\           $$$$$$$\
$$  __$$\                     \__|          $$  __$$\
$$ |  $$ | $$$$$$\   $$$$$$\  $$\  $$$$$$$\ $$ |  $$ | $$$$$$\   $$$$$$\   $$$$$$$\ $$$$$$\
$$$$$$$\ |$$  __$$\ $$  __$$\ $$ |$$  _____|$$$$$$$\ | \____$$\ $$  __$$\ $$  _____|\____$$\
$$  __$$\ $$ /  $$ |$$ |  \__|$$ |\$$$$$$\  $$  __$$\  $$$$$$$ |$$ |  \__|$$ /      $$$$$$$ |
$$ |  $$ |$$ |  $$ |$$ |      $$ | \____$$\ $$ |  $$ |$$  __$$ |$$ |      $$ |     $$  __$$ |
$$$$$$$  |\$$$$$$  |$$ |      $$ |$$$$$$$  |$$$$$$$  |\$$$$$$$ |$$ |      \$$$$$$$\\$$$$$$$ |
\_______/  \______/ \__|      \__|\_______/ \_______/  \_______|\__|       \_______|\_______|
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define PB push_back
#define MP make_pair
#define INS insert
#define LB lower_bound
#define UB upper_bound
#define pii pair <int,int>
#define pll pair <long long, long long>
#define X first
#define Y second
#define _ << " " <<
#define sz(x) (int)x.size()
#define all(a) (a).begin(),(a).end()
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORD(i, a, b) for (int i = (a); i > (b); --i)
#define FORA(i, x) for (auto &i : x)
#define REP(i, n) FOR(i, 0, n)
#define BITS(x) __builtin_popcount(x)
#define SQ(a) (a) * (a)
#define TRACE(x) cout << #x " = " << (x) << '\n';
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define umap unordered_map

typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
typedef vector <pii> vpi;
typedef vector <ll> vll;
typedef vector <pll> vpl;
typedef vector <string> vs;

const int MOD = 1e9 + 7;
const double PI = acos(-1);
const int INF = 1e9 + 10;
const ll INFL = 1e18 + 10;
const int ABC = 30;

inline int sum(int a, int b){
	if (a + b < 0)
		return (a + b + MOD) % MOD;
	return (a + b) % MOD;
}

inline void add(int &a, int b){
	a = sum(a, b);
}

inline int mul(ll a, ll b){
	return ((a % MOD) * ((ll)b % MOD)) % MOD;
}

inline int sub(int a, int b){
	return (a - b + MOD) % MOD;
}

inline int fast_pot(ll pot, ll n){
	ll ret = 1;
	while (n){
		if (n & 1LL)
			ret = (ret * pot) % MOD;
		pot = (pot * pot) % MOD;
		n >>= 1LL;
	}
	return ret;
}

const int N = 3e5 + 10;
int n, q, on[N];

struct query{
	int t;
	int l, r;
} Q[N];

namespace prvi{
	int ans[N];
	void solve(){
		REP(j, q){
			if (Q[j].t == 2){
				bool ok = 1;
				FOR(k, Q[j].l, Q[j].r){
					if (!on[k])
						ok = 0;
				}
				if (ok)
					ans[j]++;
			}
		}
		REP(i, q){
			if (Q[i].t == 1){
				on[Q[i].l] = 1 - on[Q[i].l];
			} else
				cout << ans[i] << '\n';
			REP(j, q){
				if (Q[j].t == 2){
					bool ok = 1;
					FOR(k, Q[j].l, Q[j].r){
						if (!on[k])
							ok = 0;
					}
					if (ok)
						ans[j]++;
				}
			}
		}
	}
}

namespace drugi{
	int ans[N], lst[N];
	void solve(){
		REP(i, q){
			if (Q[i].t == 1){
				int x = Q[i].l;
				if (on[x]){
					ans[x] += i - lst[x] + 1;
					on[x] = 0;
				} else {
					lst[x] = i + 1;
					on[x] = 1;
				}
			} else {
				cout << ans[Q[i].l] + (on[Q[i].l] * (i - lst[Q[i].l] + 1)) << '\n';
			}
		}
	}
}

const int LOG = 19;
const int OFF = 1 << LOG;

namespace treci{
	struct tournament{
		int t[2 * OFF], maxi[2 * OFF], off;

		void init(int n){
			for (off = 1; off < n; off *= 2);
			memset(t, 0, sizeof t);
		}

		void upd(int x, int y){
			t[x + off]++;
			maxi[x + off] = y;
			for (int i = (x + off) / 2; i; i /= 2)
				t[i] = t[i * 2] + t[i * 2 + 1], maxi[i] = max(maxi[i * 2], maxi[i * 2 + 1]);
		}

		pii query(int node, int a, int b, int lo, int hi){
			if (a > hi || b < lo)
				return {0, 0};
			if (a >= lo && b <= hi)
				return {t[node], maxi[node]};
			int mid = (a + b) / 2;
			pii l = query(node * 2, a, mid, lo, hi);
			pii r = query(node * 2 + 1, mid + 1, b, lo, hi);
			return {l.X + r.X, max(l.Y, r.Y)};
		}
	} T;
	
	void solve(){
		T.init(n);
		REP(i, n)
			if (on[i])
				T.upd(i, 0);
		REP(i, q){
			if (Q[i].t == 1){
				T.upd(Q[i].l, i + 1);
			} else {
				pii ans = T.query(1, 0, T.off - 1, Q[i].l, Q[i].r - 1);
				if (ans.X == Q[i].r - Q[i].l)
					cout << i + 1 - ans.Y << '\n';
				else
					cout << 0 << '\n';
			}
		}
	}


}

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

	cin >> n >> q;
	REP(i, n){
		char c; cin >> c;
		on[i] = c - '0';
	}
	
	bool dva = 1;
	REP(i, q){
		string s; cin >> s;
		if (s[0] == 't'){
			int x; cin >> x;
			x--;
			Q[i].t = 1, Q[i].l = x;
		} else {
			int l, r; cin >> l >> r;
			Q[i].t = 2;
			l--, r--;
			if (r - l > 1)
				dva = 0;
			Q[i].l = l, Q[i].r = r;
		}
	}

	if (max(n, q) <= 105){
		prvi::solve();
	} else if (dva){
		drugi::solve();
	} else
		treci::solve();	

	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 4804 KB Output is correct
2 Correct 90 ms 7076 KB Output is correct
3 Correct 88 ms 7164 KB Output is correct
4 Correct 103 ms 10288 KB Output is correct
5 Correct 108 ms 9456 KB Output is correct
6 Correct 92 ms 10204 KB Output is correct
7 Correct 123 ms 7852 KB Output is correct
8 Correct 124 ms 9292 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4428 KB Output is correct
2 Correct 3 ms 4428 KB Output is correct
3 Correct 3 ms 4428 KB Output is correct
4 Correct 3 ms 4432 KB Output is correct
5 Correct 119 ms 15816 KB Output is correct
6 Correct 173 ms 16448 KB Output is correct
7 Correct 230 ms 17092 KB Output is correct
8 Correct 310 ms 19680 KB Output is correct
9 Correct 103 ms 10860 KB Output is correct
10 Correct 109 ms 11416 KB Output is correct
11 Correct 113 ms 11716 KB Output is correct
12 Correct 258 ms 15556 KB Output is correct
13 Correct 304 ms 19420 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4428 KB Output is correct
2 Incorrect 3 ms 4428 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 81 ms 4804 KB Output is correct
9 Correct 90 ms 7076 KB Output is correct
10 Correct 88 ms 7164 KB Output is correct
11 Correct 103 ms 10288 KB Output is correct
12 Correct 108 ms 9456 KB Output is correct
13 Correct 92 ms 10204 KB Output is correct
14 Correct 123 ms 7852 KB Output is correct
15 Correct 124 ms 9292 KB Output is correct
16 Correct 3 ms 4428 KB Output is correct
17 Correct 3 ms 4428 KB Output is correct
18 Correct 3 ms 4428 KB Output is correct
19 Correct 3 ms 4432 KB Output is correct
20 Correct 119 ms 15816 KB Output is correct
21 Correct 173 ms 16448 KB Output is correct
22 Correct 230 ms 17092 KB Output is correct
23 Correct 310 ms 19680 KB Output is correct
24 Correct 103 ms 10860 KB Output is correct
25 Correct 109 ms 11416 KB Output is correct
26 Correct 113 ms 11716 KB Output is correct
27 Correct 258 ms 15556 KB Output is correct
28 Correct 304 ms 19420 KB Output is correct
29 Correct 3 ms 4428 KB Output is correct
30 Incorrect 3 ms 4428 KB Output isn't correct
31 Halted 0 ms 0 KB -