oj.uz

Submission #403199

# Submission time Handle Problem Language Result Execution time Memory
403199 2021-05-12T22:36:20 Z AmineTrabelsi Street Lamps (APIO19_street_lamps) C++14
20 / 100
 5000 ms 524292 KB 
// subtasks will not match always 
// for ex test case 6 of subtask 1 will be solved by sub_two
#include <bits/stdc++.h>
using namespace std;
// Hi
int n,q;
string s;
vector<pair<int,pair<int,int>>> que; // 0 toggle 1 query
void sub_one(){
    vector<vector<int>> cnt(n+5,vector<int>(n+5,0));
    vector<int> pref(n+5,0);
    for(int i=0;i<n;i++){
        pref[i+1] = pref[i]+(s[i]=='1');
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<i;j++){
            cnt[i][j] = cnt[j][i] = (pref[i]-pref[j] == i-j);
        }
    }
    for(int tt=0;tt<q;tt++){
        if(que[tt].first == 0){
            int ind = que[tt].second.first;
            if(s[ind] == '0')s[ind] = '1';
            else s[ind] = '0';
            for(int i=0;i<n;i++){
                pref[i+1] = pref[i]+(s[i]=='1');
            }
        }else{
            int a = que[tt].second.first,b = que[tt].second.second;
            cout << cnt[a][b] << '\n';
        }
        for(int i=0;i<=n;i++){
            for(int j=0;j<i;j++){
                cnt[i][j] = cnt[j][i] += (pref[i]-pref[j] == i-j);
            }
        }
    }
}
void sub_two(){
    vector<int> cnt,last_on(n+1,0);
    for(auto i:s)cnt.push_back(i-'0');
    vector<bool> on(cnt.begin(),cnt.end());
    for(int i=0;i<n;i++){
        if(on[i]){
            last_on[i] = -1;
        }else last_on[i] = 1e9+7;
    }
    for(int time=0;time<q;time++){
        if(que[time].first == 0){
            int ind = que[time].second.first;
            if(!on[ind]){
                on[ind] = 1;
                last_on[ind] = time;
                cnt[ind]++;
            }else{
                int pre = time-last_on[ind]-1;
                cnt[ind] += (pre >= 0 ? pre : 0);
                last_on[ind] = 1e9+7;
                on[ind] = 0;
            }
        }else{
            int a = que[time].second.first;
            int pre = time-last_on[a]-1;
            cout << cnt[a]+(pre >= 0 ? pre : 0) << '\n';
        }
    }
}
void sub_three(){
    // every lamp is becoming on
    cout<<"Wrong answer\n";
}
const int M = 300005;
int tree[M*4+50];
void build(int v,int tl,int tr){
    if(tl == tr){
        tree[v] = (s[tr] == '1' ? 0 : 1e9+7);
        return;
    }
    int mid = (tl+tr)/2;
    build(v*2,tl,mid);
    build(v*2+1,mid+1,tr);
    tree[v] = max(tree[v*2],tree[v*2+1]);
}
void upd(int v,int tl,int tr,int ind,int val){
    if(tl == tr && tl == val){
        tree[v] = val;
        return;
    }if(tl == tr)return;//will not happen but just in case
    int mid = (tl+tr)/2;
    if(mid <= ind){
        upd(v*2,tl,mid,ind,val);
    }else upd(v*2+1,mid+1,tr,ind,val);
    tree[v] = max(tree[v*2],tree[v*2+1]);
}
int mx(int v,int tl,int tr,int ql,int qr){
    if(ql > qr || tl > qr || tr < ql)return -(1e9+7);
    if(ql >= tl && tr <= qr){
        return tree[v];
    }
    int mid = (tl+tr)/2;
    return max(mx(v*2,tl,mid,ql,min(mid,qr)),mx(v*2+1,mid+1,tr,max(mid+1,ql),qr));
}
void sub_four(){
    // max segment tree
    build(1,0,n-1);    
    for(int time=0;time<q;time++){
        if(que[time].first == 0){
            int ind = que[time].second.first;
            upd(1,0,n-1,ind,time+1);
        }else{
            int a = que[time].second.first,b = que[time].second.second;
            int ans =  time-mx(1,0,n-1,a,b-1)+1;
            cout << (ans >= 0 ? ans : 0) << '\n';
        }
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q>>s;
    vector<bool> on;
    for(auto i:s)on.push_back((i=='1' ? 1 : 0));
    bool one = (n <= 500),two = 1,three = 0,four = 1;
    bool ex = 0;
    for(int i=0;i<q;i++){
        string t;
        cin>>t;
        if(t == "toggle"){
            if(ex)four = 0;
            int ind;
            cin>>ind;
            if(on[ind]){
                three = 0;
                on[ind] = 0;
            }else on[ind] = 1;
            que.push_back({0,{ind-1,0}});
        }else{
            ex = 1;
            int a,b;
            cin>>a>>b;
            if(b-a != 1)two = 0;
            que.push_back({1,{a-1,b-1}});
        }
    }
    if(one){
        sub_one();
    }else if(two){
        sub_two();
    }else if(four){
        sub_four();
    }else if(three)sub_three();
    else sub_one();
    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4937 ms 6708 KB Output is correct
2 Execution timed out 5064 ms 6572 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1842 ms 4312 KB Output is correct
2 Correct 1780 ms 4320 KB Output is correct
3 Correct 1831 ms 4324 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Runtime error 315 ms 524292 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 4937 ms 6708 KB Output is correct
9 Execution timed out 5064 ms 6572 KB Time limit exceeded
10 Halted 0 ms 0 KB -