oj.uz

Submission #258122

# Submission time Handle Problem Language Result Execution time Memory
258122 2020-08-05T11:52:43 Z _7_7_ Street Lamps (APIO19_street_lamps) C++14
60 / 100
 3241 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) {                        
			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("%lld%lld\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%lld", 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("%lld", &b);

			--b;

			int res = F.get(a, b);
			if (*pos.lower_bound(a) > b) 
				res += i; 			 
			printf("%lld\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("%lld%lld\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%lld", 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("%lld", &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 2816 KB Output is correct
5 Correct 2 ms 2816 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 783 ms 4112 KB Output is correct
2 Correct 845 ms 4684 KB Output is correct
3 Correct 1385 ms 17648 KB Output is correct
4 Correct 2763 ms 415444 KB Output is correct
5 Correct 2486 ms 383872 KB Output is correct
6 Correct 2530 ms 444172 KB Output is correct
7 Correct 453 ms 17704 KB Output is correct
8 Correct 182 ms 4984 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5120 KB Output is correct
2 Correct 7 ms 4736 KB Output is correct
3 Correct 6 ms 4224 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Runtime error 2324 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 3 ms 2816 KB Output is correct
2 Correct 5 ms 4096 KB Output is correct
3 Correct 7 ms 4480 KB Output is correct
4 Correct 8 ms 4608 KB Output is correct
5 Correct 515 ms 34016 KB Output is correct
6 Correct 1556 ms 330464 KB Output is correct
7 Correct 2335 ms 444308 KB Output is correct
8 Correct 3241 ms 517260 KB Output is correct
9 Correct 1075 ms 4368 KB Output is correct
10 Correct 1212 ms 3324 KB Output is correct
11 Correct 1068 ms 4248 KB Output is correct
12 Correct 1220 ms 3064 KB Output is correct
13 Correct 1049 ms 4296 KB Output is correct
14 Correct 1231 ms 3320 KB Output is correct
15 Correct 452 ms 17792 KB Output is correct
16 Correct 170 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 2816 KB Output is correct
5 Correct 2 ms 2816 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 783 ms 4112 KB Output is correct
9 Correct 845 ms 4684 KB Output is correct
10 Correct 1385 ms 17648 KB Output is correct
11 Correct 2763 ms 415444 KB Output is correct
12 Correct 2486 ms 383872 KB Output is correct
13 Correct 2530 ms 444172 KB Output is correct
14 Correct 453 ms 17704 KB Output is correct
15 Correct 182 ms 4984 KB Output is correct
16 Correct 9 ms 5120 KB Output is correct
17 Correct 7 ms 4736 KB Output is correct
18 Correct 6 ms 4224 KB Output is correct
19 Correct 2 ms 2688 KB Output is correct
20 Runtime error 2324 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -