Submission #911217

#	Time	Username	Problem	Language	Result	Execution time	Memory
911217		lighton	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	5030 ms	35680 KiB

street_lamps

#include <bits/stdc++.h>
#define forf(i,a,b) for(int i = a; i<=b; i++)
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
int N,M,Q;
char S[300001];
struct Interval{
    int s,e,ts,te;
}; vector<Interval> ints;

map<int,int> stkeyf,stkeyb;
map<int,int> enkeyf,enkeyb;
void ins(int s, int e, int t){
    int now = ints.size();
    ints.push_back({s,e, t, -1});
    stkeyf.insert({s, now});
    stkeyb.insert({-s, now});
    enkeyf.insert({e, now});
    enkeyb.insert({-e, now});
}
void ers(int ind ,int t){
    ints[ind].te = t;
    int a = ints[ind].s;
    int b = ints[ind].e;
    stkeyf.erase(stkeyf.lower_bound(a));
    stkeyb.erase(stkeyb.lower_bound(-a));
    enkeyf.erase(enkeyf.lower_bound(b));
    enkeyb.erase(enkeyb.lower_bound(-b));
}

struct Event{
    int t;
    int q;
    int s,e,v;
    bool operator<(const Event &r) const{
        return t<r.t;
    }
}; vector<Event> events;

int isq[300001];
int ans[300001];

void dnc(int s, int e){
    int m = s+e>>1;
    forf(i,s,e){
        forf(j,i+1,e){
            if(events[i].q == 0 && events[j].q == 1){
                if(events[i].s <= events[j].s && events[j].e <= events[i].e){
                    ans[events[j].t] += events[i].v;
                }
            }
        }
    }
    return;
    dnc(s,m);
    dnc(m+1,e);
}

int main(){
    scanf("%d %d" , &N,&Q);
    scanf("%s" ,S); S[N] = '0';

    {
        int l = 1;
        forf(i, 1, N) {
            if (S[i - 1] == '0' && S[i] == '1') l = i+1;
            if (S[i - 1] == '1' && S[i] == '0') {
                ins(l,i,1);
            }
        }
    }

    forf(i,2,Q+1){ // t = i
        char s[10]; int a,b;
        scanf("%s" , s);
        if(s[0] == 'q'){
            isq[i] = 1;
            scanf("%d %d" , &a,&b); b--;
            events.push_back({i,1,a,b});
            int ind = enkeyf.lower_bound(b)->second;
            if(ints[ind].s<=a && b<=ints[ind].e) ans[i] += (i - ints[ind].ts);
        }
        else{
            scanf("%d" , &a);
            if(S[a-1] == '0'){
                S[a-1] = '1';
                int l = a, r = a;
                int indl = stkeyb.lower_bound(-a)->second;
                int indr = enkeyf.lower_bound(a)->second;
                if(ints[indl].e+1 == a){
                    ers(indl,i-1);
                    l = ints[indl].s;
                }
                if(ints[indr].s-1 == a){
                    ers(indr,i-1);
                    r = ints[indr].e;
                }
                ins(l,r,i);
            }
            else{
                S[a-1] = '0';
                int ind = enkeyf.lower_bound(a)->second;
                ers(ind,i-1);
                if(ints[ind].s < a) ins(ints[ind].s , a-1 , i);
                if(ints[ind].e > a) ins(a+1 , ints[ind].e , i);
            }
        }
    }

    for(auto i : ints){
        if(i.te != -1) events.push_back({i.te,0,i.s,i.e,i.te-i.ts+1});
    }
    sort(all(events));
    dnc(0,events.size()-1);

    forf(i,1,Q+1){
        if(isq[i]) printf("%d\n" , ans[i]);
    }
}

Compilation message (stderr)

street_lamps.cpp: In function 'void dnc(int, int)':
street_lamps.cpp:45:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |     int m = s+e>>1;
      |             ~^~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     scanf("%d %d" , &N,&Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     scanf("%s" ,S); S[N] = '0';
      |     ~~~~~^~~~~~~~~
street_lamps.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         scanf("%s" , s);
      |         ~~~~~^~~~~~~~~~
street_lamps.cpp:79:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |             scanf("%d %d" , &a,&b); b--;
      |             ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:85:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |             scanf("%d" , &a);
      |             ~~~~~^~~~~~~~~~~

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