oj.uz

답안 #258131

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
258131 2020-08-05T12:04:07 Z _7_7_ 가로등 (APIO19_street_lamps) C++14
60 / 100
 3284 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 + 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') {
				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: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:170: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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 1 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 1 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 1 ms 2688 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 279 ms 3832 KB Output is correct
2 Correct 373 ms 4344 KB Output is correct
3 Correct 851 ms 13352 KB Output is correct
4 Correct 2327 ms 415352 KB Output is correct
5 Correct 2280 ms 383808 KB Output is correct
6 Correct 2579 ms 444408 KB Output is correct
7 Correct 521 ms 17776 KB Output is correct
8 Correct 297 ms 4984 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3968 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 2195 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

# 결과 실행 시간 메모리 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 485 ms 34296 KB Output is correct
6 Correct 1423 ms 330820 KB Output is correct
7 Correct 2188 ms 444328 KB Output is correct
8 Correct 3284 ms 517024 KB Output is correct
9 Correct 402 ms 3704 KB Output is correct
10 Correct 304 ms 2936 KB Output is correct
11 Correct 393 ms 3796 KB Output is correct
12 Correct 302 ms 3064 KB Output is correct
13 Correct 389 ms 3576 KB Output is correct
14 Correct 306 ms 2936 KB Output is correct
15 Correct 423 ms 17656 KB Output is correct
16 Correct 170 ms 4988 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 1 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 1 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 1 ms 2688 KB Output is correct
8 Correct 279 ms 3832 KB Output is correct
9 Correct 373 ms 4344 KB Output is correct
10 Correct 851 ms 13352 KB Output is correct
11 Correct 2327 ms 415352 KB Output is correct
12 Correct 2280 ms 383808 KB Output is correct
13 Correct 2579 ms 444408 KB Output is correct
14 Correct 521 ms 17776 KB Output is correct
15 Correct 297 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 4 ms 3456 KB Output is correct
19 Correct 2 ms 2688 KB Output is correct
20 Runtime error 2195 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -