oj.uz

Submission #258133

# Submission time Handle Problem Language Result Execution time Memory
258133 2020-08-05T12:07:28 Z _7_7_ Street Lamps (APIO19_street_lamps) C++14
60 / 100
 3169 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[10];
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 2 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 2 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 282 ms 3832 KB Output is correct
2 Correct 368 ms 4268 KB Output is correct
3 Correct 759 ms 13304 KB Output is correct
4 Correct 2407 ms 415864 KB Output is correct
5 Correct 2489 ms 384088 KB Output is correct
6 Correct 2549 ms 444372 KB Output is correct
7 Correct 546 ms 17656 KB Output is correct
8 Correct 169 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 3 ms 3456 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Runtime error 2347 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 2816 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 536 ms 34296 KB Output is correct
6 Correct 1513 ms 330488 KB Output is correct
7 Correct 2237 ms 444336 KB Output is correct
8 Correct 3169 ms 516984 KB Output is correct
9 Correct 411 ms 3576 KB Output is correct
10 Correct 320 ms 2816 KB Output is correct
11 Correct 404 ms 3576 KB Output is correct
12 Correct 315 ms 2816 KB Output is correct
13 Correct 423 ms 3576 KB Output is correct
14 Correct 324 ms 2816 KB Output is correct
15 Correct 439 ms 17656 KB Output is correct
16 Correct 173 ms 5008 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2 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 282 ms 3832 KB Output is correct
9 Correct 368 ms 4268 KB Output is correct
10 Correct 759 ms 13304 KB Output is correct
11 Correct 2407 ms 415864 KB Output is correct
12 Correct 2489 ms 384088 KB Output is correct
13 Correct 2549 ms 444372 KB Output is correct
14 Correct 546 ms 17656 KB Output is correct
15 Correct 169 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 3 ms 3456 KB Output is correct
19 Correct 2 ms 2688 KB Output is correct
20 Runtime error 2347 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -