oj.uz

Submission #139544

# Submission time Handle Problem Language Result Execution time Memory
139544 2019-08-01T01:37:55 Z eriksuenderhauf Street Lamps (APIO19_street_lamps) C++11
0 / 100
 3627 ms 198832 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int INF = 1e9 + 7;
const int MAXN = 3e5 + 5;
char str[MAXN], tmp[20];
int a[MAXN], segcnt, root[MAXN], n, q;
int seg[MAXN*18*18], L[MAXN*18*18], R[MAXN*18*18];
struct query {
	int a, b, t;

	bool operator<(const query rhs) const {
		return a < rhs.a;
	}
};

set<query> act;

void upd(int l, int r, int& k, int x, int y, int v) {
	if (!k) k = ++segcnt;
	if (x <= l && r <= y) { seg[k] += v; return; }
	int m = (l+r) / 2;
	if (x <= m) upd(l,m,L[k],x,y,v);
	if (m < y) upd(m+1,r,R[k],x,y,v);
}

int segqry(int l, int r, int k, int x) {
	if (x <= l && r <= x) return seg[k];
	int m = (l+r) / 2;
	return seg[k] + (x <= m ? segqry(l,m,L[k],x) : segqry(m+1,r,R[k],x));
}

void updF(int ind, int l, int r, int v) {
	while (ind < MAXN) {
		upd(1,n,root[ind],l,r,v);
		ind += ind & -ind;
	}
}

int qryF(int ind, int idx) {
	int ret = 0;
	while (ind) {
		ret += segqry(1,n,root[ind],idx);
		ind -= ind & -ind;
	}
	return ret;
}

int main() {
	clock_t tim = clock();
	scanf("%d %d", &n, &q);
	scanf("%s", str+1);
	for (int i = 1; i <= n; i++) a[i] = str[i]-'0';
	for (int i = 1, j = 1; i <= n+1; i = j + 1) {
		for (j = i; j <= n && a[j]; j++);
		act.insert({i,j,0});
	}
	for (int j = 1; j <= q; j++) {
		scanf("%s", tmp);
		if (tmp[0] == 't') {
			int idx;
			scanf("%d", &idx);
			if (a[idx]) {
				query cur = *prev(act.lower_bound({idx+1,0,0}));
				updF(cur.a, cur.a, cur.b, j-cur.t);
				updF(cur.b+1, cur.a, cur.b, -(j-cur.t));
				act.erase(cur);
				act.insert({cur.a,idx,j});
				act.insert({idx+1,cur.b,j});
			} else {
				int lo = idx, hi = idx;
				{
					query cur = *prev(act.lower_bound({idx+1,0,0}));
					lo = cur.a;
					updF(cur.a, cur.a, cur.b, j-cur.t);
					updF(cur.b+1, cur.a, cur.b, -(j-cur.t));
					act.erase(cur);
				}
				{
					query cur = *prev(act.lower_bound({idx+2,0,0}));
					hi = cur.b;
					updF(cur.a, cur.a, cur.b, j-cur.t);
					updF(cur.b+1, cur.a, cur.b, -(j-cur.t));
					act.erase(cur);
				}
				act.insert({lo,hi,j});
			}
			a[idx] ^= 1;
		} else {
			int lo, hi;
			scanf("%d %d", &lo, &hi);
			int ans = qryF(lo, hi);
			query cur = *prev(act.lower_bound({lo+1,0,0}));
			if (hi <= cur.b)
				ans += j-cur.t;
			printf("%d\n",ans);
		}
	}
	//cerr << clock() - tim << "\n";;
	return 0;
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:56:10: warning: unused variable 'tim' [-Wunused-variable]
  clock_t tim = clock();
          ^~~
street_lamps.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", str+1);
  ~~~~~^~~~~~~~~~~~~
street_lamps.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", tmp);
   ~~~~~^~~~~~~~~~~
street_lamps.cpp:68:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &idx);
    ~~~~~^~~~~~~~~~~~
street_lamps.cpp:97:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &lo, &hi);
    ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 534 ms 1396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1016 KB Output is correct
2 Correct 6 ms 1016 KB Output is correct
3 Correct 5 ms 860 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3627 ms 198832 KB Output is correct
6 Correct 3067 ms 170636 KB Output is correct
7 Correct 2164 ms 130908 KB Output is correct
8 Correct 326 ms 9744 KB Output is correct
9 Incorrect 117 ms 4088 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 4 ms 764 KB Output is correct
3 Correct 6 ms 760 KB Output is correct
4 Correct 7 ms 888 KB Output is correct
5 Correct 749 ms 23544 KB Output is correct
6 Correct 1427 ms 100176 KB Output is correct
7 Correct 2060 ms 127280 KB Output is correct
8 Correct 3100 ms 145892 KB Output is correct
9 Incorrect 797 ms 4228 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -