Submission #570623

#	Time	Username	Problem	Language	Result	Execution time	Memory
570623		patrikpavic2	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	2639 ms	329312 KiB

street_lamps

/**
* user:  ppavic
* fname: Patrik
* lname: Pavić
* task:  street-light
* score: 100.0
* date:  2019-07-06 10:35:14.642573
*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <unordered_map>
#include <ext/pb_ds/assoc_container.hpp>
 
#define X first
#define Y second
#define PB push_back
 
using namespace __gnu_pbds;
using namespace std;
 
typedef long long ll;
typedef pair < int, int > pii;
typedef vector < int > vi;
typedef vector < pii > vp;
 
 
const int NN = 3e5 + 500;
const int M = 1e6 + 500;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int LOG = 19;
const int OFF = (1 << LOG);
const int SVE = 2e7 + 500;
 
int n, m, POS, K, K2, I, FL;
 
struct node{
	int L, R;
	int sm = 0, sm2 = 0;
};

node N[SVE];
int TKO = 1;
 
int loga1[2 * OFF], loga2[2 * OFF];
 
void update(int cur, int a,int b){
	N[cur].sm += K, N[cur].sm2 += K2;
	//printf("%d %d += %d\n", a, b, k);
	if(a == b) return;
	if(I <= (a + b) / 2) {
		if(N[cur].L == 0) N[cur].L = TKO++;
		update(N[cur].L, a, (a + b) / 2);
		return;
	}
	if(N[cur].R == 0) N[cur].R = TKO++;
	update(N[cur].R, (a + b) / 2 + 1, b);
}
 
int get(int cur, int a,int b){
	if(cur == 0 || a > I) return 0;
	if(b <= I) {
		if(!FL) return N[cur].sm;
		else return POS * N[cur].sm2 - N[cur].sm;
	}
	return get(N[cur].L, a, (a + b) / 2) + get(N[cur].R, (a + b) / 2 + 1, b);
}
 
inline void dodaj(int x,int y,int k){
	y = n - y + 10; x += 10;
	for(; x < NN; x += x & -x){
		if(loga1[x] == 0) loga1[x] = TKO++;
		I = y, K = k, K2 = 0;
		update(loga1[x], 0, OFF - 1);
	}
}
 
inline int nadi(int x,int y){
	y = n - y + 10; x += 10;
	int ret = 0;
	for(; x ; x -= x & -x){
		I = y, FL = 0;
		ret += get(loga1[x], 0, OFF - 1);
	}
	//printf("ret = %d\n", ret);
	return ret;
}
 
inline void dodaj2(int x,int y,int k,int k2){
	y = n - y + 10; x += 10;
	for(; x < NN; x += x & -x){
		if(loga2[x] == 0) loga2[x] = TKO++;
		I = y, K = k, K2 = k2;
		update(loga2[x], 0, OFF - 1);
	}
}
 
inline int nadi2(int x,int y,int k){
	y = n - y + 10; x += 10; POS = k;
	ll ret = 0;
	for(; x ; x -= x & -x){
		I = y, FL = 1;
		ret += get(loga2[x], 0, OFF - 1);
	}
	//printf("ret = %d\n", ret);
	return ret;
}
 
 
 
set < pii > gr;
int A[NN], L[M], R[M], tren[M], c = 0;
 
int nadi_interval(int x){
	if(x < 0 || x >= n || !A[x]) return -1;
	return (gr.lower_bound({x, 0})) -> Y;
}
 
void makni_interval(int x, int i){
	//printf("Nestaje interval [%d %d], ind = %d tren %d sad %d\n", L[x], R[x], x, tren[x], i);
	dodaj2(L[x], R[x], -tren[x], -1);
	dodaj(L[x], R[x], i - tren[x]);
	gr.erase({R[x], x});
}
 
void dodaj_interval(){
	//printf("Dolazi interval [%d %d], ind = %d tren %d\n", L[c], R[c], c, tren[c]);
	dodaj2(L[c], R[c], tren[c],1);
	gr.insert({R[c], c}); c++;
}
 
int main(){
	scanf("%d%d", &n, &m);
	for(int i = 0;i < n;i++){
		char c; scanf(" %c", &c);
		A[i] = c - '0';
	}
	for(int i = 0;i < n;){
		if(!A[i]){
			i++; continue;
		}
		int j = i;
		for(; j < n && A[j]; j++);
		L[c] = i, R[c] = j - 1; tren[c] = 0;
		dodaj_interval();
		i = j;
	}
	for(int i = 1;i <= m;i++){
		char str[10]; scanf("%s", str);
		if(str[0] == 'q'){
			int l, r; scanf("%d%d", &l, &r); l--, r--, r--;
			//printf("%d %d %d\n", pas.nadi(l, r), cnt_akt.nadi(l, r), akt.nadi(l, r));
			printf("%d\n", nadi(l, r) + nadi2(l, r, i));
		}
		else{
			int x; scanf("%d", &x); x--;
			if(!A[x]){
				int lft = nadi_interval(x - 1);
				int rig = nadi_interval(x + 1);
				int nL = x, nR = x;
				if(lft != -1){
					nL = L[lft];
					makni_interval(lft, i);
				}
				if(rig != -1) {
					nR = R[rig];
					makni_interval(rig, i);
				}
				L[c] = nL, R[c] = nR; tren[c] = i; 
				dodaj_interval();
			}
			else{
				int moj = nadi_interval(x);
				makni_interval(moj, i);
				if(L[moj] != x){
					L[c] = L[moj], R[c] = x - 1, tren[c] = i;
					dodaj_interval();
				}
				if(R[moj] != x){
					L[c] = x + 1, R[c] = R[moj], tren[c] = i;
					dodaj_interval();
				}		
				
			}
			A[x] = !A[x];
		}
	}
	return 0;
}
 

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:139:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
street_lamps.cpp:141:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |   char c; scanf(" %c", &c);
      |           ~~~~~^~~~~~~~~~~
street_lamps.cpp:155:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |   char str[10]; scanf("%s", str);
      |                 ~~~~~^~~~~~~~~~~
street_lamps.cpp:157:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |    int l, r; scanf("%d%d", &l, &r); l--, r--, r--;
      |              ~~~~~^~~~~~~~~~~~~~~~
street_lamps.cpp:162:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |    int x; scanf("%d", &x); x--;
      |           ~~~~~^~~~~~~~~~

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