oj.uz

Submission #865963

# Submission time Handle Problem Language Result Execution time Memory
865963 2023-10-25T06:39:15 Z jk410 Street Lamps (APIO19_street_lamps) C++17
20 / 100
 195 ms 30008 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,CntQ;
vector<query> QV;
string S;
set<interval> Set;
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;
}
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;
            }
        }
    }
    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);
                QV.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;
                    QV.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;
                    QV.push_back({it->r,0,it->l,t-it->t});
                    Set.erase(it);
                }
                Set.insert(cur);
            }
        }
        else{
            CntQ++;
            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[CntQ]+=t-prev(it)->t;
            QV.push_back({r-1,-1,CntQ,l});
            QV.push_back({N,1,CntQ,l});
        }
    }
    stable_sort(all(QV),[&](query a,query b)->bool{
        return a.t<b.t;
    });
    for (query i:QV){
        if (i.mode)
            Ans[i.x]+=fenwickQuery(i.y)*i.mode;
        else
            fenwickUpdate(i.x,i.y);
    }
    for (int i=1; i<=CntQ; i++)
        cout<<Ans[i]<<"\n";
    return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 97 ms 18616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 194 ms 30008 KB Output is correct
6 Correct 187 ms 25288 KB Output is correct
7 Correct 190 ms 21936 KB Output is correct
8 Correct 195 ms 20176 KB Output is correct
9 Correct 99 ms 17124 KB Output is correct
10 Correct 90 ms 13976 KB Output is correct
11 Correct 99 ms 16560 KB Output is correct
12 Correct 87 ms 13840 KB Output is correct
13 Correct 103 ms 16828 KB Output is correct
14 Correct 88 ms 14264 KB Output is correct
15 Correct 113 ms 22716 KB Output is correct
16 Correct 116 ms 26312 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -