oj.uz

Submission #264626

# Submission time Handle Problem Language Result Execution time Memory
264626 2020-08-14T08:04:44 Z dimash241 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 3504 ms 193748 KB 
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
 
//# include <x86intrin.h>
# include <bits/stdc++.h>
 
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;
 
template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red
 
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void setIO(string s = "") {
	// cin.exceptions(cin.failbit); 
	// throws exception when do smth illegal
	// ex. try to read letter into int
	if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}
 
const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 3e5 + 3;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;
 
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
 
int rnd (int l, int r) {
	return uniform_int_distribution<int> (l, r)(gen);
}
 
set < array<int,3> > act;
//on segments l, r, st_time
int n, m;
string s;
 
int t[N*18*18];
int L[N*18*18];
int R[N*18*18];
int root[N];
 
int ptr;
 
void updQuery (int l, int r, int x, int &v, int tl = 1, int tr = N) {
	if (tl > r || l > tr || l > r) return;
	if (!v) v = ++ptr;
	if (l <= tl && tr <= r) {
		t[v] += x;
		return;
	}
	
	int tm = (tl+tr)>>1;
	updQuery(l, r, x, L[v], tl, tm);
	updQuery(l, r, x, R[v], tm+1, tr);
}
 
int getQuery (int p, int v, int tl = 1, int tr = N) {
	if (tl == tr || !v) {
		return t[v];
	}
	
	int tm = (tl+tr)>>1;
	
	if(p <= tm) return t[v] + getQuery(p, L[v], tl, tm);
	
	return t[v] + getQuery(p, R[v], tm+1, tr);
}
 
int getCalc (int v, int r) {
	int res = 0;
	while(v) {
		res += getQuery(r, root[v]);
		v -= v&-v;
	}
	return res;
}
 
void updRec (int v, int l, int r, int x) {
	while(v < N) {
		updQuery(l, r, x, root[v]);
		v += v&-v;
	}
}

void Rem (array<int, 3> cur, int t) {
	assert(cur[0] <= cur[1]);
	updRec (cur[0], cur[0], cur[1], t-cur[2]);
	updRec (cur[1]+1, cur[0], cur[1], cur[2]-t);
}
 
void turn_off (int pos, int i) {
	auto cur = *prev(act.lb({pos+1, 0, 0}));
	Rem(cur, i);
	
	act.erase(cur);
	act.insert({cur[0], pos, i});
	act.insert({pos+1, cur[1], i});
}
 
void turn_on (int pos, int i) {
	auto curL = *prev(act.lb({pos+1, 0, 0}));
	auto curR = *prev(act.lb({pos+2, 0, 0}));
	
	Rem(curL, i);
	Rem(curR, i);
	
	act.erase(curL);
	act.erase(curR);
	act.insert({curL[0], curR[1], i});
}
 
int main () {
	SpeedForce;
	
	cin >> n >> m >> s;
	s='0'+s;
	for (auto &e : s) e -= '0';
	
	for (int i = 1; i <= n; ) {
		{
			int j = i;
			while(j <= n && s[j]) ++j;
			act.insert({i, j, 0});
			i = j+1;
		}
	}
	
	for (int i = 1; i <= m; ++i) {
		string op;
		cin >> op;
		
		if (op[0] == 't') {
			int pos;
			cin >> pos;
			if(s[pos]) turn_off(pos, i);
			else turn_on(pos, i);
			
			
			s[pos] ^= 1;
		} else {
			int l, r;
			cin >> l >> r;
			//in rectangle x = {1, l} y = {1, r} 
			int ans = getCalc(l, r);
			auto cur = *prev(act.lb({l+1, 0, 0}));
			if (cur[1] >= r) ans += i-cur[2];
			
			cout << ans << '\n';
		}
	}
	
	
	return Accepted;
}
 
// B...a

Compilation message

street_lamps.cpp: In function 'void setIn(std::string)':
street_lamps.cpp:34:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   34 | void setIn(string s) { freopen(s.c_str(),"r",stdin); }
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'void setOut(std::string)':
street_lamps.cpp:35:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   35 | void setOut(string s) { freopen(s.c_str(),"w",stdout); }
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 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 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 40 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1152 KB Output is correct
2 Correct 8 ms 1024 KB Output is correct
3 Correct 5 ms 896 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 3504 ms 193748 KB Output is correct
6 Correct 2811 ms 165284 KB Output is correct
7 Correct 1774 ms 125924 KB Output is correct
8 Correct 145 ms 2788 KB Output is correct
9 Incorrect 95 ms 1272 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 5 ms 896 KB Output is correct
4 Correct 8 ms 896 KB Output is correct
5 Correct 480 ms 18656 KB Output is correct
6 Correct 1279 ms 95184 KB Output is correct
7 Correct 2114 ms 122068 KB Output is correct
8 Correct 2963 ms 140752 KB Output is correct
9 Correct 1561 ms 992 KB Output is correct
10 Runtime error 36 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 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 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Runtime error 40 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -