Submission #121342

#	Time	Username	Problem	Language	Result	Execution time	Memory
121342		WhipppedCream	Street Lamps (APIO19_street_lamps)	C++17	40 / 100	5044 ms	402540 KiB

street_lamps

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
     
const int maxn = 3e5+5;
     
int st[4*maxn];
int arr[maxn];
char s[maxn];
int n;
     
int rng[maxn];

int ask(int i, int j)
{
	int res = 0;
	for(int x = j; x; x -= x&(-x)) res += rng[x];
	for(int x = i-1; x; x -= x&(-x)) res -= rng[x];
	return res;
}
     
void update(int x, int dx)
{
	for(; x<= n; x += x&(-x)) rng[x] += dx;
}
     
int q;
    
int A[maxn], B[maxn];

struct node
{
	int val;
	node *left, *right;
	node()
	{
		val = 0;
		left = right = NULL;
	}
	node* getL()
	{
		if(left == NULL) left = new node();
		return left;
	}
	node* getR()
	{
		if(right == NULL) right = new node();
		return right;
	}
	void update(int x, int dx, int p = 1, int L = 1, int R = n+1)
	{
		if(x> R || x< L) return;
		if(L == R) 
		{
			val += dx;
			// printf("[%d, %d] is %d\n", L, R, val);
			return;
		}
		int M = (L+R)/2;
		if(x<= M) getL()->update(x, dx, 2*p, L, (L+R)/2);
		else getR()->update(x, dx, 2*p+1, (L+R)/2+1, R);
		val = (left?left->val:0)+(right?right->val:0);
		// printf("[%d, %d] is %d\n", L, R, val);
	}
	int ask(int i, int j, int p = 1, int L = 1, int R = n+1)
	{
		if(i> R || j< L) return 0;
		if(i<= L && R<= j)
		{
			// printf("[%d, %d] is %d\n", L, R, val);
			return val;
		}
		int x = left?left->ask(i, j, 2*p, L, (L+R)/2):0;
		int y = right?right->ask(i, j, 2*p+1, (L+R)/2+1, R):0;
		return x+y;
	}
};

node* ft[maxn];

void updatems(int x, int y, int dx)
{
	// printf("go %d %d %d\n", x, y, dx);
	for(; x<= n+1; x += x&(-x))
	{
		ft[x]->update(y, dx);
		// printf("update ft[%d] at %d by %d\n", x, y, dx);
	}
}

int askms(int x1, int y1, int x2, int y2)
{
	int res = 0;
	for(int x = x2; x; x -= x&(-x)) res += ft[x]->ask(y1, y2);
	// printf("res is %d\n", ft[1]->ask(1, 6));
	return res;
}

void updateme(int x1, int y1, int x2, int y2, int dx)
{
    updatems(x1, y1, dx);
    updatems(x2+1, y1, -dx);
    updatems(x1, y2+1, -dx);
    updatems(x2+1, y2+1, dx);
}
    
int ezreal(int x, int y)
{
    return askms(1, 1, x, y);
}
    
bool con(int a, int b)
{
    return ask(a, b-1) == b-a;
}
     
void toggle(int x, int tim, bool upd)
{
    int lo = 1, hi = x;
    while(lo< hi)
    {
        int mid = (lo+hi)/2;
        if(con(mid, x)) hi = mid;
        else lo = mid+1;
    }
    int L = lo;
    lo = x+1, hi = n+1;
    while(lo< hi)
    {
        int mid = (lo+hi+1)/2;
        if(con(x+1, mid)) lo = mid;
        else hi = mid-1;
    }
    int R = lo;
    if(arr[x])
    {
        arr[x] = 0;
        updateme(L, x+1, x, R, tim);
    }
    else
    {
        arr[x] = 1;
        updateme(L, x+1, x, R, -tim);
        // printf("go %d %d %d %d %d\n", L, x+1, x, R, -tim);
    }
    update(x, arr[x] == 1?1:-1);
}
     
int main()
{
    scanf("%d %d", &n, &q);
    scanf("%s", s+1);
    for(int tim = 1; tim<= q; tim++)
    {
        A[tim] = B[tim] = -1;
        char t[10];
        scanf("%s", t+1);
        if(t[1] == 't')
        {
            scanf("%d", &A[tim]);
        }
        else
        {
            scanf("%d %d", &A[tim], &B[tim]);
        }
    }
    for(int i = 1; i<= n; i++)
    {
        if(s[i] == '1')
        {
            update(i, 1);
            arr[i] = 1;
        }
    }
    for(int i = 1; i<= n+1; i++) ft[i] = new node();
    for(int tim = 1; tim<= q; tim++)
    {
        if(B[tim] == -1) 
        {
            int x = A[tim];
            toggle(x, tim, 1);
            continue;
        }
        int x = A[tim], y = B[tim];
        bool cc = con(x, y);
        // printf("con = %d\n", ezreal(x, y));
        if(cc) printf("%d\n", tim+ezreal(x, y)+1-1);
        else printf("%d\n", ezreal(x, y));
    }
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:157:10: 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:158:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s+1);
     ~~~~~^~~~~~~~~~~
street_lamps.cpp:163:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", t+1);
         ~~~~~^~~~~~~~~~~
street_lamps.cpp:166:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &A[tim]);
             ~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:170:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &A[tim], &B[tim]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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