Submission #209223

#	Time	Username	Problem	Language	Result	Execution time	Memory
209223		mieszko11b	Street Lamps (APIO19_street_lamps)	C++14	60 / 100	249 ms	15096 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;

int n, q;
char c[107][107];
int before[300007], last0[300007];
char cc[300007];
int a[300007], b[300007];
int d[1200007];
int lv;

void insert(int w, int x) {
	w += lv;
	d[w] = x;
	w /= 2;
	while(w) {
		d[w] = max(d[2 * w], d[2 * w + 1]);
		w /= 2;
	}
}

int query(int a, int b) {
	if(a > b) return 1e9;
	int va = a +lv;
	int vb = b + lv;
	int res = max(d[va], d[vb]);
	while(va / 2 != vb/  2) {
		if(va % 2 == 0)
			res = max(res, d[va + 1]);
		if(vb % 2 == 1)
			res = max(res, d[vb - 1]);
		va /= 2;
		vb /= 2;
	}
	return res;
}


int main() {
	scanf("%d%d", &n, &q);
	if(n <= 100 && q <= 100) {
		scanf(" %s", c[0] + 1);
		for(int i = 1 ; i <= q ; i++) {
			char comm[10];
			
			for(int j = 1 ; j <= n ; j++)	
				c[i][j] = c[i - 1][j];
			
			scanf(" %s", comm);
			if(comm[0] == 'q') {
				int a, b;
				scanf("%d%d", &a, &b);
				int res = 0;
				for(int j = 0 ; j < i ; j++) {
					bool ok = true;
					for(int k = a ; k < b ; k++)
						if(c[j][k] == '0')
							ok = false;
					if(ok) res++;
				}
				printf("%d\n", res);
			} else {
				int w;
				scanf("%d", &w);
				
				if(c[i][w] == '0') c[i][w] = '1';
				else c[i][w] = '0';
			}
		}
		return 0;
	}
	
	scanf(" %s", cc + 1);
	
	bool kosno = true;
	
	for(int i = 1 ; i <= q ; i++) {
		char comm[10];
		scanf(" %s", comm);
		if(comm[0] == 'q') {
			int a, b;
			scanf("%d%d", &a, &b);
			::a[i] = a;
			::b[i] = b;
			if(b != a + 1)
				kosno = false;
		} else {
			int w;
			scanf("%d", &w);
			::a[i] = -1;
			::b[i] = w;
		}				
	}
	
	if(kosno) {
		memset(last0, -1, sizeof last0);
		
		for(int i = 1 ; i <= q ; i++) {
			if(a[i] != -1) {
				int a = ::a[i];
				int b = ::b[i];
				int res = before[a];
				if(cc[a] == '1')
					res += i - last0[a] - 1;
				printf("%d\n", res);
			} else {
				int w = b[i];
				if(cc[w] == '1') {
					before[w] += i - last0[w] - 1;
					cc[w] = '0';
				} else {
					last0[w] = i - 1;
					cc[w] = '1';
				}
			}
		}
		return 0;
	}
	
	lv = 2;
	while(lv < n + 2)
		lv *= 2;
		
	for(int i = 1 ; i < 2 * lv ; i++)
		d[i] = 1e9;
		
	for(int i = 1 ; i <= n ; i++)
		if(cc[i] == '1')
			insert(i, 0);
		
	for(int i = 1 ; i <= q ; i++) {
		if(a[i] != -1) {
			int a = ::a[i];
			int b = ::b[i];
			
			int q = query(a, b - 1);
			printf("%d\n", max(0, i - q));
		} else {
			int w = b[i];
			insert(w, i);
		}
	}
	
	return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:102:9: warning: unused variable 'b' [-Wunused-variable]
     int b = ::b[i];
         ^
street_lamps.cpp:41: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:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %s", c[0] + 1);
   ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:50:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %s", comm);
    ~~~~~^~~~~~~~~~~~~
street_lamps.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &a, &b);
     ~~~~~^~~~~~~~~~~~~~~~
street_lamps.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &w);
     ~~~~~^~~~~~~~~~
street_lamps.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %s", cc + 1);
  ~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %s", comm);
   ~~~~~^~~~~~~~~~~~~
street_lamps.cpp:83:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &a, &b);
    ~~~~~^~~~~~~~~~~~~~~~
street_lamps.cpp:90:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &w);
    ~~~~~^~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20