Submission #249028

#	Time	Username	Problem	Language	Result	Execution time	Memory
249028		sealnot123	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	1542 ms	99864 KiB

street_lamps

#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
#define FOR(i, a, b) for(int i=(a); i<=(b); ++i)
#define ROF(i, a, b) for(int i=(a); i>=(b); --i)
#define make_unique(a) sort(all((a))), (a).resize(unique(all((a)))-(a).begin())

using namespace std;

typedef pair<int,int> PII;
typedef long long LL;
typedef double DD;
typedef long double LD;
typedef pair<LL,LL> PLL;
typedef pair<DD,DD> PDD;
typedef vector<int> VI;
typedef vector<LL> VL;

const int N = 300003;
set< pair<PII, int> > segments; // (l,r), when
set< pair<PII, int> >::iterator it;
vector<int> value_fw[N], fw[N];
vector< pair<PII, int> > to_update[N];
int ans[N], current_state[N], L[N], R[N];
int n;
char s[N];
void build_fw(int i, int j){
    while(i <= n){
        value_fw[i].pb(-j);
        i += (i&-i);
    }
}
void add(int i, int j, int v){
    j = -j;
    while(i <= n){
        int idx = upper_bound(all(value_fw[i]), j)-value_fw[i].begin();
        while(idx < SZ(fw[i])){
            fw[i][idx] += v;
            idx += (idx&-idx);
        }
        i += (i&-i);
    }
}
int get(int i, int j){
    j = -j;
    int sum = 0;
    while(i > 0){
        int idx = upper_bound(all(value_fw[i]), j)-value_fw[i].begin();
        while(idx > 0){
            sum += fw[i][idx];
            idx -= (idx&-idx);
        }
        i -= (i&-i);
    }
    return sum;
}
void connect(int i, int t){
    //printf("connect %d at %d\n",i,t);
    current_state[i] = 1;
    pair< PII, int > to_insert = { PII(i,i), t };
    PII p;
    int v;
    if(i < n && current_state[i+1]){
        it = segments.lower_bound({PII(i+1,0),0});
        tie(p, v) = *it;
        to_update[t].pb( {p, t-v} );
        build_fw(p.x, p.y);
        to_insert.x.y = p.y;
        segments.erase(it);
    }
    if(i > 1 && current_state[i-1]){
        it = segments.lower_bound({PII(i,0),0});
        --it;
        tie(p, v) = *it;
        to_update[t].pb( {p, t-v} );
        build_fw(p.x, p.y);
        to_insert.x.x = p.x;
        segments.erase(it);
    }
    segments.insert(to_insert);
}
void cut(int i, int t){
    //printf("cut %d at %d\n",i,t);
    current_state[i] = 0;
    it = segments.lower_bound({PII(i+1,0),0});
    --it;
    PII p;
    int v;
    tie(p, v) = *it;
    build_fw(p.x, p.y);
    to_update[t].pb( {p, t-v} );
    segments.erase(it);
    if(i < n && current_state[i+1]){
        segments.insert({PII(i+1,p.y),t});   
    }
    if(i > 1 && current_state[i-1]){
        segments.insert({PII(p.x,i-1),t});
    }
}
char cmd[10];
void solve(){
    int q;
    scanf("%d %d",&n,&q);
    scanf(" %s",s+1);
    FOR(i, 1, n){
        if(s[i] == '1') connect(i, 0);
    }
    FOR(i, 1, q){
        int a, b;
        scanf(" %s %d",cmd,&a);
        if(cmd[0] == 't'){
            if(current_state[a]) cut(a, i);
            else connect(a, i);
        }else{
            scanf("%d",&b);
            --b;
            L[i] = a, R[i] = b;
            // check if there is existing segment
            it = segments.lower_bound({PII(a+1,0),0});
            if(it != segments.begin()){
                --it;
                PII p;
                int v;
                tie(p, v) = *it;
                if(p.x <= a && b <= p.y){
                    ans[i] += i-v;
                }
            }
        }
        //printf("segments: ");
        //for(auto e : segments){
        //    printf("(%d, %d) ",e.x.x, e.x.y);
        //}
        //puts("");
    }
    // build fenwick
    FOR(i, 1, n){
        make_unique(value_fw[i]);
        fw[i].resize(SZ(value_fw[i])+1);
    }
    FOR(i, 1, q){
        for(auto e : to_update[i]){
            add(e.x.x, e.x.y, e.y);
        }
        if(L[i] == 0) continue;
        ans[i] += get(L[i], R[i]);
        printf("%d\n",ans[i]);
    }
}

int main(){
    solve();
	return 0;
}
/*
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

Compilation message (stderr)

street_lamps.cpp: In function 'void solve()':
street_lamps.cpp:107: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:108:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %s",s+1);
     ~~~~~^~~~~~~~~~~
street_lamps.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %s %d",cmd,&a);
         ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:119:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&b);
             ~~~~~^~~~~~~~~

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