oj.uz

Submission #258130

# Submission time Handle Problem Language Result Execution time Memory
258130 2020-08-05T12:02:03 Z _7_7_ Street Lamps (APIO19_street_lamps) C++14
60 / 100
 3157 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;
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 + 1) {                        
			if (!T[x])
				T[x] = new ST(1, n + 1);
			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);
	F.inc(xa, yb, -z);
	F.inc(xb, ya, -z);
	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') {
				int x, y;
				auto it = pos.lower_bound(a);
				y = *it;
				--it;
				x = *it;

				++x, --y;

				update(x, a, a, y, i);
				pos.insert(a);
			} else {
				int x, y;
				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:130:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:131: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:143: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:172: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 275 ms 3832 KB Output is correct
2 Correct 374 ms 4228 KB Output is correct
3 Correct 801 ms 13304 KB Output is correct
4 Correct 2328 ms 415396 KB Output is correct
5 Correct 2171 ms 383796 KB Output is correct
6 Correct 2455 ms 444384 KB Output is correct
7 Correct 448 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 3968 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 2147 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 5 ms 3712 KB Output is correct
5 Correct 490 ms 34168 KB Output is correct
6 Correct 1580 ms 330672 KB Output is correct
7 Correct 2217 ms 444520 KB Output is correct
8 Correct 3157 ms 517112 KB Output is correct
9 Correct 405 ms 3576 KB Output is correct
10 Correct 309 ms 2816 KB Output is correct
11 Correct 409 ms 3636 KB Output is correct
12 Correct 319 ms 2892 KB Output is correct
13 Correct 404 ms 3704 KB Output is correct
14 Correct 308 ms 2940 KB Output is correct
15 Correct 444 ms 17656 KB Output is correct
16 Correct 185 ms 4984 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 275 ms 3832 KB Output is correct
9 Correct 374 ms 4228 KB Output is correct
10 Correct 801 ms 13304 KB Output is correct
11 Correct 2328 ms 415396 KB Output is correct
12 Correct 2171 ms 383796 KB Output is correct
13 Correct 2455 ms 444384 KB Output is correct
14 Correct 448 ms 17656 KB Output is correct
15 Correct 169 ms 4984 KB Output is correct
16 Correct 5 ms 3968 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 2147 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -