oj.uz

Submission #392578

# Submission time Handle Problem Language Result Execution time Memory
392578 2021-04-21T10:45:44 Z BorisBarca Street Lamps (APIO19_street_lamps) C++14
40 / 100
 128 ms 13144 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';
			}
		}
	}
}


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';
	}

	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--;
			Q[i].l = l, Q[i].r = r;
		}
	}


	if (max(n, q) <= 105){
		prvi::solve();
	} else
		drugi::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 77 ms 4692 KB Output is correct
2 Correct 83 ms 8228 KB Output is correct
3 Correct 88 ms 8768 KB Output is correct
4 Correct 104 ms 13144 KB Output is correct
5 Correct 107 ms 12488 KB Output is correct
6 Correct 94 ms 12932 KB Output is correct
7 Correct 121 ms 11588 KB Output is correct
8 Correct 128 ms 12852 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 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 77 ms 4692 KB Output is correct
9 Correct 83 ms 8228 KB Output is correct
10 Correct 88 ms 8768 KB Output is correct
11 Correct 104 ms 13144 KB Output is correct
12 Correct 107 ms 12488 KB Output is correct
13 Correct 94 ms 12932 KB Output is correct
14 Correct 121 ms 11588 KB Output is correct
15 Correct 128 ms 12852 KB Output is correct
16 Incorrect 1 ms 332 KB Output isn't correct
17 Halted 0 ms 0 KB -