Submission #949922

#	Time	Username	Problem	Language	Result	Execution time	Memory
949922		idiotcomputer	Street Lamps (APIO19_street_lamps)	C++11	100 / 100	2764 ms	264456 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first 
#define s second
#define pb push_back
#define sz size

const int mxN = 3e5+1;
int n;

bool vals[mxN];
vector<pii> ranges[mxN];
vector<int> indexs[mxN];
int cnt = 0;

int lazsum[4*(20*mxN)+1];

void sumupd(int tl, int tr, int v, int l = 0, int r = cnt-1, int idx = 0){
    if (tl > tr) return;
    if (l > tr || r < tl) return;
    if (l >= tl && r <= tr){
        lazsum[idx] += v;
        return;
    }
    int m = (l+r)/2;
    sumupd(tl,tr,v,l,m,2*idx+1);
    sumupd(tl,tr,v,m+1,r,2*idx+2);
}

int sumquery(int t, int l = 0, int r = cnt-1, int idx = 0){
    if (l > t || r < t){
        return 0;
    }
    if (l == r) return lazsum[idx];
    int m = (l+r)/2;
    return sumquery(t,l,m,2*idx+1) + sumquery(t,m+1,r,2*idx+2) + lazsum[idx];
}

//containing ordered queries in a spec. range
vector<pii> all[4*mxN+1];
int sidx[4*mxN+1];

void build(int l = 0, int r = n-1, int idx = 0){
    if (l == r){
        sidx[idx] = cnt;
        for (pii i : ranges[l]){
            all[idx].pb(i);
            indexs[i.s].pb(cnt);
            cnt++;
        }
        return;
    }
    int m = (l+r)/2;
    build(l,m,2*idx+1);
    build(m+1,r,2*idx+2);
    sidx[idx] = cnt;
    int cidx = 0;
    while (cidx < all[2*idx+2].sz() && all[2*idx+2][cidx].f <= r){
        cidx++;
    }
    for (pii i : all[2*idx+1]){
        if (i.f <= r) continue;
        while (cidx < all[2*idx+2].sz() && all[2*idx+2][cidx].f < i.f){
            all[idx].pb(all[2*idx+2][cidx]);
            indexs[all[2*idx+2][cidx].s].pb(cnt);
            cnt++;
            cidx++;
        }
        all[idx].pb(i);
        indexs[i.s].pb(cnt);
        cnt++;
    }
    while (cidx < all[2*idx+2].sz()){
        all[idx].pb(all[2*idx+2][cidx]);
        indexs[all[2*idx+2][cidx].s].pb(cnt);
        cnt++;
        cidx++;
    }
  /*  cout << l << "-" << r << " " << idx << " : ";
    for (pii temp : all[idx]) cout << temp.f << ',' << temp.s << " ";
    cout << '\n';*/
}

void qupd(int tl, int tr, int t, int v, int l = 0, int r = n-1, int idx = 0){
    if (l > tr || r < tl) return;
    if (l >= tl && r <= tr){
        pii temp = {tr,mxN+1};
        int fidx = lower_bound(all[idx].begin(),all[idx].end(),temp) - all[idx].begin();
        temp = {t,mxN+1};
        int lidx = lower_bound(all[idx].begin(),all[idx].end(),temp) - all[idx].begin();
        sumupd(sidx[idx]+fidx,sidx[idx]+lidx-1,v);
        return;
    }
    int m = (l+r)/2;
    qupd(tl,tr,t,v,l,m,2*idx+1);
    qupd(tl,tr,t,v,m+1,r,2*idx+2);
}

// all for fiding the bounds of a connected range
int laz[4*mxN+1][2];

void pdown(int idx, int w){
    if (laz[idx][w] != -1){
        laz[2*idx+1][w] = laz[idx][w];
        laz[2*idx+2][w] = laz[idx][w];
    }
    laz[idx][w] = -1;
}

int query(int t, int w, int l = 0, int r = n-1, int idx = 0){
    if (l > t || r < t) return -1;
    if (l == r) return laz[idx][w];
    pdown(idx,w);
    int m = (l+r)/2;
    int r1 = query(t,w,l,m,2*idx+1);
    int r2 = query(t,w,m+1,r,2*idx+2);
    if (r1 == -1) return r2;
    return r1;
}

void bupd(int tl, int tr, int v, int w, int l = 0, int r = n-1, int idx = 0){
    if (l > tr || r < tl) return;
    if (l >= tl && r <= tr){
        laz[idx][w] = v;
        return;
    }
    pdown(idx,w);
    int m = (l+r)/2;
    bupd(tl,tr,v,w,l,m,2*idx+1);
    bupd(tl,tr,v,w,m+1,r,2*idx+2);
}

void upd(int t, int v, int l = 0, int r = n-1, int idx = 0){
    if (l > t || r < t) return;
    if (l == r){
       // cout << t << " - " << v << ' ';
        if (vals[l]){
            int lidx = query(l,0);
            int ridx = query(l,1);
           // cout << lidx << " " << ridx;
            qupd(lidx,l,ridx,v);
            vals[l] = false;
            bupd(l+1,ridx,l+1,0);
            bupd(lidx,l,l,1);
        } else {
            int lidx = query(l,0);
            int ridx = query(l+1,1);
          //  cout << lidx << " " << ridx;
            qupd(lidx,l,ridx,-1*v);
            vals[l] = true;
            bupd(l+1,ridx,lidx,0);
            bupd(lidx,l,ridx,1);
        }
       // cout << '\n';
        return;
    }
    int m = (l+r)/2;
    upd(t,v,l,m,2*idx+1);
    upd(t,v,m+1,r,2*idx+2);
}


int main()
{
    memset(lazsum,0,sizeof(lazsum));
    memset(sidx,0,sizeof(sidx));
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int q;
    cin >> n >> q;
    n++;
    
    string s1;
    cin >> s1;
    for (int i =0; i < 4*mxN+1; i++) for (int j =0; j < 2; j++) laz[i][j] = -1;
    for (int i =0; i < n; i++){
        bupd(i,i,i,0);
        bupd(i,i,i,1);
    }
    
    vector<pii> qu(q);
    int curr = 0;
    string s2;
    for (int i =0; i <q; i++){
        cin >> s2;
        if (s2 == "toggle"){
            cin >> qu[i].f;
            qu[i].f -= 1;
            qu[i].s = -1;
        } else {
            cin >> qu[i].f >> qu[i].s;
            qu[i].f -= 1;
            qu[i].s -= 1;
            ranges[qu[i].f].pb({qu[i].s,curr});
            curr++;
        }
    }
    for (int i =0; i < n; i++){
        sort(ranges[i].begin(),ranges[i].end());
    }
    build();
  /*   cout << '\n';
    for (int i =0; i < curr; i++){
        cout << i << ": ";
        for (int j : indexs[i]) cout << j << "  ";
        cout << '\n';
    }
    cout << '\n';*/
    for (int i =0; i < n-1; i++){
        vals[i] = false;
        if (s1[i] == '1'){
            upd(i,0);
        }
    }
    
   /* for (int i =0; i < n; i++){
        cout << query(i,0) << "-" << query(i,1) << " ";
    }
    cout << '\n';
   */
    
    curr = 0;
    int res;
    for (int i = 0; i < q; i++){
        if (qu[i].s == -1){
            upd(qu[i].f,i+1);
     /*       for (int j =0; j< n; j++){
            cout << query(j,0) << "-" << query(j,1) << " ";
        }
        cout << '\n';
   */
        } else {
            res = 0;
            for (int j : indexs[curr]){
                res += sumquery(j);
            }
          //  cout << qu[i].s << " " << qu[i].f << ' ' << query(qu[i].s,1) << "\n";
            if (query(qu[i].s,0) <= qu[i].f) res += i+1;
            cout << res << '\n';
            curr++;
        }
    }
    
    return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'void build(int, int, int)':
street_lamps.cpp:59:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     while (cidx < all[2*idx+2].sz() && all[2*idx+2][cidx].f <= r){
      |            ~~~~~^~~~~~~~~~~~~~~~~~~
street_lamps.cpp:64:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         while (cidx < all[2*idx+2].sz() && all[2*idx+2][cidx].f < i.f){
      |                ~~~~~^~~~~~~~~~~~~~~~~~~
street_lamps.cpp:74:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     while (cidx < all[2*idx+2].sz()){
      |            ~~~~~^~~~~~~~~~~~~~~~~~~

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