oj.uz

Submission #258124

# Submission time Handle Problem Language Result Execution time Memory
258124 2020-08-05T11:54:15 Z _7_7_ Street Lamps (APIO19_street_lamps) C++14
40 / 100
 3126 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 = 1e6 + 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 4 ms 8224 KB Output is correct
2 Correct 4 ms 8192 KB Output is correct
3 Correct 5 ms 8192 KB Output is correct
4 Correct 4 ms 8320 KB Output is correct
5 Correct 5 ms 8320 KB Output is correct
6 Correct 4 ms 8192 KB Output is correct
7 Correct 4 ms 8192 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 865 ms 9592 KB Output is correct
2 Correct 938 ms 10232 KB Output is correct
3 Correct 1613 ms 24056 KB Output is correct
4 Correct 2671 ms 464072 KB Output is correct
5 Correct 2413 ms 424340 KB Output is correct
6 Correct 2903 ms 495412 KB Output is correct
7 Correct 493 ms 23308 KB Output is correct
8 Correct 181 ms 10488 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10880 KB Output is correct
2 Correct 10 ms 10368 KB Output is correct
3 Correct 10 ms 9856 KB Output is correct
4 Correct 4 ms 8192 KB Output is correct
5 Runtime error 2220 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8320 KB Output is correct
2 Correct 8 ms 9728 KB Output is correct
3 Correct 10 ms 10112 KB Output is correct
4 Correct 12 ms 10368 KB Output is correct
5 Correct 534 ms 42676 KB Output is correct
6 Correct 1785 ms 370916 KB Output is correct
7 Correct 3126 ms 495768 KB Output is correct
8 Runtime error 2943 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8224 KB Output is correct
2 Correct 4 ms 8192 KB Output is correct
3 Correct 5 ms 8192 KB Output is correct
4 Correct 4 ms 8320 KB Output is correct
5 Correct 5 ms 8320 KB Output is correct
6 Correct 4 ms 8192 KB Output is correct
7 Correct 4 ms 8192 KB Output is correct
8 Correct 865 ms 9592 KB Output is correct
9 Correct 938 ms 10232 KB Output is correct
10 Correct 1613 ms 24056 KB Output is correct
11 Correct 2671 ms 464072 KB Output is correct
12 Correct 2413 ms 424340 KB Output is correct
13 Correct 2903 ms 495412 KB Output is correct
14 Correct 493 ms 23308 KB Output is correct
15 Correct 181 ms 10488 KB Output is correct
16 Correct 12 ms 10880 KB Output is correct
17 Correct 10 ms 10368 KB Output is correct
18 Correct 10 ms 9856 KB Output is correct
19 Correct 4 ms 8192 KB Output is correct
20 Runtime error 2220 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -