Submission #125471

#	Time	Username	Problem	Language	Result	Execution time	Memory
125471		arnold518	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	4255 ms	484964 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3e5;
const int MAXVAL = 2e7;

int N, Q, A[MAXN+10];

set<int> S, E;

void operator += (pll &p, pll q) { p.first+=q.first, p.second+=q.second; }

pll range(int pos)
{
    pll ret;
    auto it=S.upper_bound(pos); it--; ret.first=*it;
    auto jt=E.lower_bound(pos); ret.second=*jt;
    return ret;
}

struct Node
{
    ll val; int one, pos;
    int lc, rc;
    Node() : lc(-1), rc(-1), val(0), one(0), pos(-1) {}
};

int cnt;
Node tree[MAXVAL];

void update1(int node, int tl, int tr, int x, ll val, int one)
{
    //printf("?:%d %d %d %d %lld %d\n", node, tl, tr, x, val, one);
    if(tl==tr)
    {
        tree[node].val+=val;
        tree[node].one+=one;
        return;
    }
    int mid=tl+tr>>1;

    if(tree[node].pos!=-1)
    {
        if(tree[node].pos<=mid)
        {
            tree[node].lc=cnt++;
            tree[tree[node].lc].pos=tree[node].pos;
            tree[tree[node].lc].val+=tree[node].val;
            tree[tree[node].lc].one+=tree[node].one;
        }
        else
        {
            tree[node].rc=cnt++;
            tree[tree[node].rc].pos=tree[node].pos;
            tree[tree[node].rc].val+=tree[node].val;
            tree[tree[node].rc].one+=tree[node].one;
        }
        tree[node].pos=-1;
    }

    if(x<=mid)
    {
        if(tree[node].lc==-1)
        {
            tree[node].lc=cnt++;
            tree[tree[node].lc].pos=x;
            tree[tree[node].lc].val+=val;
            tree[tree[node].lc].one+=one;
        }
        else
        {
            update1(tree[node].lc, tl, mid, x, val, one);
        }
    }
    else
    {
        if(tree[node].rc==-1)
        {
            tree[node].rc=cnt++;
            tree[tree[node].rc].pos=x;
            tree[tree[node].rc].val+=val;
            tree[tree[node].rc].one+=one;
        }
        else
        {
            update1(tree[node].rc, mid+1, tr, x, val, one);
        }
    }
    tree[node].val+=val;
    tree[node].one+=one;
}

pll query1(int node, int tl, int tr, int l, int r)
{
    //printf("%d %d %d %d %d %d %lld %d\n", node, tl, tr, l, r, tree[node].pos, tree[node].val, tree[node].one);
    if(r<tl || tr<l) return {0, 0};
    if(l<=tl && tr<=r) return {tree[node].val, tree[node].one};
    int mid=tl+tr>>1;
    if(tree[node].pos!=-1)
    {
        if(l<=tree[node].pos && tree[node].pos<=r) return {tree[node].val, tree[node].one};
        else return {0, 0};
    }
    pll ret;
    if(tree[node].lc!=-1) ret+=query1(tree[node].lc, tl, mid, l, r);
    if(tree[node].rc!=-1) ret+=query1(tree[node].rc, mid+1, tr, l, r);
    return ret;
}

void update2(int y, int x, ll val, int one)
{
    for(; y<=N; y+=(y&-y)) update1(y, 1, N, x, val, one);
}

pll query2(int y, int x)
{
    pll ret;
    for(; y>0; y-=(y&-y)) ret+=query1(y, 1, N, x, N);
    return ret;
}

int main()
{
    int i, j, k;

    scanf("%d%d", &N, &Q);
    for(i=1; i<=N; i++) scanf("%1d", &A[i]);

    if(A[1]==1) S.insert(1);
    if(A[N]==1) E.insert(N);
    for(i=2; i<=N; i++) if(A[i-1]==0 && A[i]==1) S.insert(i);
    for(i=1; i<=N-1; i++) if(A[i]==1 && A[i+1]==0) E.insert(i);

    cnt=N+1;

    for(auto it=S.begin(), jt=E.begin(); it!=S.end() && jt!=E.end(); it++, jt++) update2(*it, *jt, Q+1, 1);
/*
    for(auto it : S) printf("%d ", it); printf("\n");
    for(auto it : E) printf("%d ", it); printf("\n");
*/
    for(k=Q; k>=1; k--)
    {
        char s[10];
        scanf("%s", s);
        if(s[0]=='t')
        {
            int pos;
            scanf("%d", &pos);
            if(A[pos]==0)
            {
                S.insert(pos); E.insert(pos);
                if(pos!=1 && A[pos-1]==1)
                {
                    pll a=range(pos), b=range(pos-1);

                    update2(b.first, b.second, -k, -1);
                    E.erase(b.second);
                    S.erase(a.first);
                }

                if(pos!=N && A[pos+1]==1)
                {
                    pll a=range(pos), b=range(pos+1);

                    update2(b.first, b.second, -k, -1);
                    E.erase(a.second);
                    S.erase(b.first);
                }
                pll b=range(pos);
                update2(b.first, b.second, k, 1);

                A[pos]=1;
            }
            else
            {
                pll now=range(pos);

                if(now.first==now.second)
                {
                    update2(pos, pos, -k, -1);
                    S.erase(pos); E.erase(pos);
                }
                else if(pos==now.first)
                {
                    update2(now.first, now.second, -k, -1);
                    update2(pos+1, now.second, k, 1);
                    S.erase(pos);
                    S.insert(pos+1);
                }
                else if(pos==now.second)
                {
                    update2(now.first, now.second, -k, -1);
                    update2(now.first, pos-1, k, 1);
                    E.erase(pos);
                    E.insert(pos-1);
                }
                else
                {
                    update2(now.first, now.second, -k, -1);
                    update2(now.first, pos-1, k, 1);
                    update2(pos+1, now.second, k, 1);
                    S.insert(pos+1);
                    E.insert(pos-1);
                }
                A[pos]=0;
            }
        }
        else
        {
            int a, b;
            scanf("%d%d", &a, &b); b--;
            pll val=query2(a, b);
            //printf("%lld %lld\n", val.first, val.second);
            printf("%lld\n", val.first-val.second*k);
        }

        /*
        for(auto it : S) printf("%d ", it); printf("\n");
        for(auto it : E) printf("%d ", it); printf("\n");
        */
    }
}

Compilation message (stderr)

street_lamps.cpp: In constructor 'Node::Node()':
street_lamps.cpp:28:13: warning: 'Node::rc' will be initialized after [-Wreorder]
     int lc, rc;
             ^~
street_lamps.cpp:27:8: warning:   'll Node::val' [-Wreorder]
     ll val; int one, pos;
        ^~~
street_lamps.cpp:29:5: warning:   when initialized here [-Wreorder]
     Node() : lc(-1), rc(-1), val(0), one(0), pos(-1) {}
     ^~~~
street_lamps.cpp: In function 'void update1(int, int, int, int, ll, int)':
street_lamps.cpp:44:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
street_lamps.cpp: In function 'pll query1(int, int, int, int, int)':
street_lamps.cpp:102:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:128:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j, k;
            ^
street_lamps.cpp:130: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:131:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=N; i++) scanf("%1d", &A[i]);
                         ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:148:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", s);
         ~~~~~^~~~~~~~~
street_lamps.cpp:152:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &pos);
             ~~~~~^~~~~~~~~~~~
street_lamps.cpp:215:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &a, &b); b--;
             ~~~~~^~~~~~~~~~~~~~~~

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