oj.uz

Submission #392566

# Submission time Handle Problem Language Result Execution time Memory
392566 2021-04-21T10:36:51 Z BorisBarca Street Lamps (APIO19_street_lamps) C++14
20 / 100
 78 ms 4676 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];
					on[x] = 0;
				} else {
					lst[x] = i;
					on[x] = 1;
				}
			} else {
				cout << ans[Q[i].l] + (on[Q[i].l] * (i - lst[Q[i].l])) << '\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
0 / 20.0

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

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 Incorrect 78 ms 4676 KB Output isn't correct
9 Halted 0 ms 0 KB -