oj.uz

Submission #865964

# Submission time Handle Problem Language Result Execution time Memory
865964 2023-10-25T07:05:07 Z jk410 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 5000 ms 35572 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#define all(v) v.begin(),v.end()
using namespace std;
struct interval{
    int l,r,t;
    bool operator<(const interval &tmp)const{
        if (l!=tmp.l)
            return l<tmp.l;
        return r<tmp.r;
    }
};
struct query{
    int t,mode,x,y;
};
int N,Q;
string S;
set<interval> Set;
vector<query> Queries[300001];
int Ans[300001];
int Tree[300001];
void fenwickUpdate(int x,int val){
    while (x<=N){
        Tree[x]+=val;
        x+=x&-x;
    }
}
int fenwickQuery(int x){
    int ret=0;
    while (x){
        ret+=Tree[x];
        x-=x&-x;
    }
    return ret;
}
void solve(int l,int r){
    if (l==r)
        return;
    int m=(l+r)>>1;
    solve(l,m);
    solve(m+1,r);
    vector<query> qv;
    for (int i=l; i<=m; i++){
        for (query j:Queries[i]){
            if (!j.mode)
                qv.push_back(j);
        }
    }
    for (int i=m+1; i<=r; i++){
        for (query j:Queries[i]){
            if (j.mode)
                qv.push_back(j);
        }
    }
    stable_sort(all(qv),[&](query a,query b)->bool{
        return a.t<b.t;
    });
    fill(Tree+1,Tree+N+1,0);
    for (query i:qv){
        if (i.mode)
            Ans[i.x]+=fenwickQuery(i.y)*i.mode;
        else
            fenwickUpdate(i.x,i.y);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N>>Q>>S;
    for (int i=1,j=0; i<=N; i++){
        if (S[i-1]=='1'){
            if (!j)
                j=i;
            if (i==N||S[i]=='0'){
                Set.insert({j,i,0});
                j=0;
            }
        }
    }
    fill(Ans+1,Ans+Q+1,-1);
    for (int t=1; t<=Q; t++){
        string s;
        cin>>s;
        if (s[0]=='t'){
            int x;
            cin>>x;
            auto it=Set.lower_bound({x+1,x+1,0});
            if (it!=Set.begin()&&prev(it)->r>=x){//x가 켜져 있음
                interval cur=*(--it);
                Queries[t].push_back({cur.r,0,cur.l,t-cur.t});
                Set.erase(it);
                if (cur.l<x)
                    Set.insert({cur.l,x-1,t});
                if (x<cur.r)
                    Set.insert({x+1,cur.r,t});
            }
            else{//x가 꺼져 있음
                interval cur={x,x,t};
                if (it!=Set.begin()&&prev(it)->r==x-1){
                    cur.l=(--it)->l;
                    Queries[t].push_back({it->r,0,it->l,t-it->t});
                    it=Set.erase(it);
                }
                if (it!=Set.end()&&it->l==x+1){
                    cur.r=it->r;
                    Queries[t].push_back({it->r,0,it->l,t-it->t});
                    Set.erase(it);
                }
                Set.insert(cur);
            }
        }
        else{
            Ans[t]=0;
            int l,r;
            cin>>l>>r;
            r--;
            auto it=Set.lower_bound({l+1,l+1,0});
            if (it!=Set.begin()&&prev(it)->r>=r)
                Ans[t]+=t-prev(it)->t;
            Queries[t].push_back({r-1,-1,t,l});
            Queries[t].push_back({N,1,t,l});
        }
    }
    solve(1,Q);
    for (int i=1; i<=Q; i++){
        if (Ans[i]!=-1)
            cout<<Ans[i]<<"\n";
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 2 ms 9684 KB Output is correct
4 Correct 2 ms 9684 KB Output is correct
5 Correct 2 ms 9564 KB Output is correct
6 Correct 2 ms 9564 KB Output is correct
7 Correct 2 ms 9680 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 27964 KB Output is correct
2 Correct 344 ms 31420 KB Output is correct
3 Correct 441 ms 32296 KB Output is correct
4 Execution timed out 5079 ms 34484 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9560 KB Output is correct
2 Correct 3 ms 9692 KB Output is correct
3 Correct 3 ms 9560 KB Output is correct
4 Correct 3 ms 9564 KB Output is correct
5 Execution timed out 5054 ms 25048 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 3 ms 9564 KB Output is correct
3 Correct 3 ms 9564 KB Output is correct
4 Correct 3 ms 9532 KB Output is correct
5 Execution timed out 5053 ms 35572 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 2 ms 9684 KB Output is correct
4 Correct 2 ms 9684 KB Output is correct
5 Correct 2 ms 9564 KB Output is correct
6 Correct 2 ms 9564 KB Output is correct
7 Correct 2 ms 9680 KB Output is correct
8 Correct 317 ms 27964 KB Output is correct
9 Correct 344 ms 31420 KB Output is correct
10 Correct 441 ms 32296 KB Output is correct
11 Execution timed out 5079 ms 34484 KB Time limit exceeded
12 Halted 0 ms 0 KB -