Submission #532134

#	Time	Username	Problem	Language	Result	Execution time	Memory
532134		79brue	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	2242 ms	84444 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, w, idx;
    Rect(){}
    Rect(int xl, int xr, int w, int idx): xl(xl), xr(xr), w(w), idx(idx){}
};

struct Query {
    int type;
    int x, y, w, idx, t;
    Query(){}
    Query(int type, int x, int y, int w, int idx, int t): type(type), x(x), y(y), w(w), idx(idx), t(t){}

    bool operator<(const Query &r)const{
        if(t != r.t) return t<r.t;
        return type < r.type;
    }
};

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

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],
                                          interval.lower_bound(Interval(xl+1, qx[i], 0))->s, i));
                    interval.erase(interval.lower_bound(Interval(xl+1, qx[i], 0)));
                }
                if(xr != qx[i]+1){
                    rectangles.push_back(Rect(qx[i]+1, xr,
                                              interval.lower_bound(Interval(qx[i]+1, xr, 0))->s, i));
                    interval.erase(interval.lower_bound(Interval(qx[i]+1, xr, 0)));
                }

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

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

                if(xl != qx[i]-1){
                    interval.insert(Interval(xl+1, qx[i], i));
                }
                if(xr != qx[i]+1){
                    interval.insert(Interval(qx[i]+1, xr, 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;
        }
    }
}


struct QueryRect {
    int qt; /// 1: 더하기, 2: 답 계산
    int x, y, w, idx;
    QueryRect(){}
    QueryRect(int qt, int x, int y, int w, int idx): qt(qt), x(x), y(y), w(w), idx(idx){}

    bool operator<(const QueryRect &r)const{
        if(y != r.y) return y<r.y;
        return qt<r.qt;
    }
};

struct Fenwick {
    const int n = 300005;
    int tree[300010];

    void add(int x, int y){
        x++;
        while(x<=n){
            tree[x] += y;
            x += x&-x;
        }
    }

    int sum(int x){
        x++;
        int ret = 0;
        while(x){
            ret += tree[x];
            x -= x&-x;
        }
        return ret;
    }
} tree;

void processQueries(int l, int r){
    if(l==r) return;
    int m = (l+r)>>1;
    processQueries(l, m);
    processQueries(m+1, r);

    vector<QueryRect> vec;
    for(int i=l; i<=m; i++){
        if(queries[i].type == 1){
            vec.push_back(QueryRect(1, queries[i].x, queries[i].y, queries[i].w, queries[i].idx));
        }
    }
    for(int i=m+1; i<=r; i++){
        if(queries[i].type == 2){
            vec.push_back(QueryRect(2, queries[i].x, queries[i].y, queries[i].w, queries[i].idx));
        }
    }
    sort(vec.begin(), vec.end());

    for(QueryRect qrect: vec){
        if(qrect.qt == 1){ /// 덧셈 쿼리
            tree.add(qrect.x, qrect.w);
        }
        else{
            ans[qrect.idx] += tree.sum(qrect.x);
        }
    }
    for(QueryRect qrect: vec){
        if(qrect.qt == 1) tree.add(qrect.x, -qrect.w);
    }
}

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]);
            queries.push_back(Query(2, qx[i], qy[i], 1, i, i));
        }
    }

    makeIntervals();
    for(Rect rect: rectangles){
        queries.push_back(Query(1, rect.xr+1, rect.xr+1, rect.idx-rect.w, 0, rect.idx));
        queries.push_back(Query(1, rect.xl, rect.xr+1, -(rect.idx-rect.w), 0, rect.idx));
        queries.push_back(Query(1, rect.xr+1, rect.xl, -(rect.idx-rect.w), 0, rect.idx));
        queries.push_back(Query(1, rect.xl, rect.xl, rect.idx-rect.w, 0, rect.idx));
    }
    sort(queries.begin(), queries.end());

//    for(Query query: queries){
//        printf("%d %d %d %d %d %d\n", query.type, query.x, query.y, query.w, query.idx, query.t);
//    }
    processQueries(0, (int)queries.size()-1);

    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:174:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  174 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:175:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |     for(int i=1; i<=n; i++) scanf("%1d", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~
street_lamps.cpp:181:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  181 |             scanf("%d", &qx[i]);
      |             ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:185:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |             scanf("%d %d", &qx[i], &qy[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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