oj.uz

Submission #258135

# Submission time Handle Problem Language Result Execution time Memory
258135 2020-08-05T12:12:33 Z _7_7_ Street Lamps (APIO19_street_lamps) C++17
60 / 100
 3141 ms 524292 KB 
#include <bits/stdc++.h>                                           
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
//#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;  
typedef unsigned long long ull;         
typedef vector < pii > vpii;                                   	
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;
 
typedef tree < int, null_type, less < int >, rb_tree_tag, tree_order_statistics_node_update > ordered_set;
 
const int inf = 1e9, maxn = 2e5 + 48, mod = 998244353, N = 3e5 + 12;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 300;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = acos(-1);
const ll INF = 1e18;
 
int n, q, a, b, x, y;
char s[N], t[6];
set < int > pos;


struct ST {
	int tl, tr, sum;
	ST *l, *r;

	ST () {}
	
	ST (int lf, int rg) {
		tl = lf, tr = rg;
		sum = 0;
		l = r = NULL;
	}


	void update (int pos, int x) {
	   	sum += x;

		if (tl == tr)
			return;

		int tm = (tl + tr) >> 1;			
		if (pos <= tm) {
			if (!l)
				l = new ST(tl, tm);
			l->update(pos, x);
			return;
		}

		if (!r)
			r = new ST(tm + 1, tr);
		r->update(pos, x);
	}

	int get (int lf, int rg) {
		if (lf > rg || tl > rg || lf > tr)
			return 0;
		if (lf <= tl && tr <= rg)
			return sum;
	
		return (!l ? 0 : l->get(lf, rg)) + (!r ? 0 : r->get(lf, rg));
	}
};


struct BIT {
	ST *T[N];

	BIT () {
		memset(T, 0, sizeof(T));
	}

	void inc (int x, int y, int z) {
		while (x <= n) {                        
			if (!T[x])
				T[x] = new ST(1, n);
			T[x]->update(y, z);
			x |= x + 1;
		}
	}

	int get (int x, int y) {
	    int res = 0;
		while (x > 0) {
			if (T[x]) 
				res += T[x]->get(1, y); 			 			
			x = (x & (x + 1)) - 1;
		}

		return res;
	}
} F;
 
void update (int xa, int ya, int xb, int yb, int z) {
//	cerr << xa << ' ' << ya << ' ' << xb << ' ' << yb << ' ' << z << endl;
    ++xb, ++yb;
	F.inc(xa, ya, z);
	if (yb <= n)
		F.inc(xa, yb, -z);
	if (xb <= n)
		F.inc(xb, ya, -z);
	if (xb <= n && yb <= n)
		F.inc(xb, yb, z);
}


main () {
	scanf("%d%d\n%s", &n, &q, s + 1);

	
	for (int i = 1; i <= n; ++i)
		if (s[i] == '0') 
			pos.insert(i);

	pos.insert(0);
	pos.insert(n + 1);
	
	
	for (int i = 1; i <= q; ++i) {
		scanf("\n%s%d", t, &a);
		if (t[0] == 't') {
			if (s[a] == '1') {
				auto it = pos.lower_bound(a);
				y = *it;
				--it;
				x = *it;

				++x, --y;

				update(x, a, a, y, i);
				pos.insert(a);
			} else {
				pos.erase(a);

				auto it = pos.lower_bound(a);
				y = *it;
				--it;
				x = *it;


				++x, --y;
				update(x, a, a, y, -i);
			}

			s[a] = '0' + '1' - s[a];
		} else {
			scanf("%d", &b);

			--b;

			int res = F.get(a, b);
			if (*pos.lower_bound(a) > b) 
				res += i; 			 
			printf("%d\n", res);
		}
	}

}

Compilation message

street_lamps.cpp:133:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:134:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d\n%s", &n, &q, s + 1);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:146:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("\n%s%d", t, &a);
   ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:173:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &b);
    ~~~~~^~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 3852 KB Output is correct
2 Correct 372 ms 4220 KB Output is correct
3 Correct 925 ms 13304 KB Output is correct
4 Correct 2332 ms 415404 KB Output is correct
5 Correct 2438 ms 383948 KB Output is correct
6 Correct 2927 ms 444332 KB Output is correct
7 Correct 453 ms 17912 KB Output is correct
8 Correct 171 ms 4984 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3840 KB Output is correct
2 Correct 4 ms 3712 KB Output is correct
3 Correct 4 ms 3456 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Runtime error 2165 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 3 ms 3328 KB Output is correct
3 Correct 4 ms 3456 KB Output is correct
4 Correct 4 ms 3712 KB Output is correct
5 Correct 486 ms 34320 KB Output is correct
6 Correct 1508 ms 330488 KB Output is correct
7 Correct 2231 ms 444280 KB Output is correct
8 Correct 3141 ms 517080 KB Output is correct
9 Correct 415 ms 3576 KB Output is correct
10 Correct 325 ms 2964 KB Output is correct
11 Correct 404 ms 3576 KB Output is correct
12 Correct 317 ms 2816 KB Output is correct
13 Correct 410 ms 3580 KB Output is correct
14 Correct 326 ms 2816 KB Output is correct
15 Correct 514 ms 17656 KB Output is correct
16 Correct 176 ms 4984 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 3 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 270 ms 3852 KB Output is correct
9 Correct 372 ms 4220 KB Output is correct
10 Correct 925 ms 13304 KB Output is correct
11 Correct 2332 ms 415404 KB Output is correct
12 Correct 2438 ms 383948 KB Output is correct
13 Correct 2927 ms 444332 KB Output is correct
14 Correct 453 ms 17912 KB Output is correct
15 Correct 171 ms 4984 KB Output is correct
16 Correct 5 ms 3840 KB Output is correct
17 Correct 4 ms 3712 KB Output is correct
18 Correct 4 ms 3456 KB Output is correct
19 Correct 2 ms 2688 KB Output is correct
20 Runtime error 2165 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -