Submission #532063

#	Time	Username	Problem	Language	Result	Execution time	Memory
532063		79brue	Street Lamps (APIO19_street_lamps)	C++14	0 / 100	169 ms	12264 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Interval {
    int l, r, s;
    Interval(){}
    Interval(int l, int r, int s): l(l), r(r), s(s){}

    bool operator<(const Interval &r)const{
        return l<r.l;
    }
};

struct Rect{
    int xl, xr, yl, yr;
    Rect(){}
    Rect(int xl, int xr, int yl, int yr): xl(xl), xr(xr), yl(yl), yr(yr){}
};

struct Query{
    int xl, xr, y; bool in; int num;
    Query(){}
    Query(int xl, int xr, int y, bool in, int num): xl(xl), xr(xr), y(y), in(in), num(num){}

    bool operator<(const Query &r)const{
        return y<r.y;
    }
};

int n, q;
int arr[300002];
int qt[300002], qx[300002], qy[300002];
set<Interval> interval;
int ans[300002];

vector<Rect> rectangles;
vector<Query> queries;

void makeIntervals(){
    set<int> off;
    off.insert(0), off.insert(n+1);
    for(int i=1; i<=n; i++){
        if(!arr[i]) off.insert(i);
    }

    for(int i=1; i<=n; i++){
        if(!arr[i]) continue;
        int j = i;
        while(j<n && arr[j+1]) j++;
        interval.insert(Interval(i, j, 0));
        i=j;
    }

    for(int i=1; i<=q; i++){
        if(qt[i] == 0){
            if(!arr[qx[i]]){ /// OFF -> ON
                auto it = off.lower_bound(qx[i]);
                int xl = *prev(it), xr = *next(it);
                off.erase(it);
                arr[qx[i]] = 1;
                if(xl != qx[i]-1){
                    rectangles.push_back(Rect(xl+1, qx[i]-1,
                                          interval.lower_bound(Interval(xl+1, qx[i]-1, 0))->s, i));
                    interval.erase(interval.lower_bound(Interval(xl+1, qx[i]-1, 0)));
                }
                if(xr != qx[i]+1){
                    rectangles.push_back(Rect(qx[i]+1, xr-1,
                                              interval.lower_bound(Interval(qx[i]+1, xr-1, 0))->s, i));
                    interval.erase(interval.lower_bound(Interval(qx[i]+1, xr-1, 0)));
                }

                interval.insert(Interval(xl+1, xr-1, i));
            }
            else{ /// ON -> OFF
                auto it = off.lower_bound(qx[i]);
                int xl = *prev(it), xr = *it;
                off.insert(qx[i]);
                arr[qx[i]] = 0;

                rectangles.push_back(Rect(xl+1, xr-1, interval.lower_bound(Interval(xl+1, xr-1, 0))->s, i));

                if(xl != qx[i]-1){
                    interval.insert(Interval(xl+1, qx[i]-1, i));
                }
                if(xr != qx[i]+1){
                    interval.insert(Interval(qx[i]+1, xr-1, i));
                }
            }
        }
        else{
            auto toff = off.lower_bound(qx[i]);
            if(*toff < qy[i]) continue;
            auto it = interval.lower_bound(Interval(*prev(toff)+1, *toff-1, 0));
            ans[i] += i - it->s;
        }
    }

    for(Interval p: interval){
        rectangles.push_back(Rect(p.l, p.r, p.s, q));
    }
}

void processQueries(){

}

int main(){
    scanf("%d %d", &n, &q);
    for(int i=1; i<=n; i++) scanf("%1d", &arr[i]);
    for(int i=1; i<=q; i++){
        string str;
        cin >> str;
        if(str[0] == 't'){
            qt[i] = 0;
            scanf("%d", &qx[i]);
        }
        else{
            qt[i] = 1;
            scanf("%d %d", &qx[i], &qy[i]);
        }
    }

    makeIntervals();
    processQueries();

    for(int i=1; i<=q; i++){
        if(qt[i] == 1) printf("%d\n", ans[i]);
    }
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:111:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:112:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |     for(int i=1; i<=n; i++) scanf("%1d", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~
street_lamps.cpp:118:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |             scanf("%d", &qx[i]);
      |             ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:122:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |             scanf("%d %d", &qx[i], &qy[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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