oj.uz

Submission #255858

# Submission time Handle Problem Language Result Execution time Memory
255858 2020-08-02T02:05:07 Z balbit Street Lamps (APIO19_street_lamps) C++14
0 / 100
 5000 ms 21256 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

#define pii pair<int, int>
#define f first
#define s second

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<" "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x ){ cerr<<x<<endl; }
template<typename T, typename ...S> void _do(T && x , S&&...y){ cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define endl '\n'
#define bug(...)
#endif // BALBIT

const int maxn = 3e5+5;

//vector<pii> g[maxn];
bool hi[maxn];
int ps[maxn];
int ans[maxn], lt[maxn];

struct ty{
    int l, r, need, id;
};

struct grp{
    int l, r;
    vector<ty> v;
};

int s[maxn];

int QU(int e) {
//    bug(e);C
    int re = 0;
    for (++e; e>0; e -= e&-e) re += s[e];
    return re;
}

void MO(int e, int v) {
    if (e == -1) return;
    for (++e; e<maxn; e+=e&-e) s[e] += v;
}

signed main(){
    IOS();
    int n,q; cin>>n>>q;

    for (int i = 0; i<n; ++i) {
        char c; cin>>c;
        hi[i] = c=='1';
        if (hi[i]) {
            lt[i] = -1;
        }
        ps[i+1] = ps[i] + hi[i];
    }
    vector<pii> chg;
    grp org = {-1,q+1, {}};
    for (int i = 0; i<q; ++i) {
        string s; cin>>s;
        if (s[0] == 'q') {
            int a,b; cin>>a>>b; --a; --b; --b;
            org.v.pb({a,b,(b-a+1)-(ps[b+1] - ps[a]), i});
            bug(org.v.back().need);
        }else{
            int x; cin>>x;
            chg.pb({i,x-1});

        }
    }
    chg.pb({q+1000, -1});
    vector<int> ans(q,-2);

    queue<grp> qq;
    qq.push(org);
    set<int> hv;
    int now = 0;
    while (!qq.empty()){
        grp g = qq.front(); qq.pop();
        bug(g.l, g.r);
        if (g.l == g.r) {
            for (auto x : g.v) {
                ans[x.id] = g.l;
            }
            continue;
        }
        int mid = (g.l + g.r+2)/2-1;
        if (chg[now].f > mid) {
            now = 0; memset(s, 0, sizeof s);
        }
        while (chg[now].f <= mid) {
            bug("HI");
            MO(chg[now].s,1); ++now;
        }
        grp tol = {g.l,mid,{}}, tor = {mid+1,g.r,{}};
        for (auto x : g.v) {
            bug("hmmmm");
            int btw = QU(x.r) - QU(x.l-1);
            if (btw >= x.need) tol.v.pb(x);
            else tor.v.pb(x);
        }
        bug("enddd");
        qq.push(tol); qq.push(tor);
    }
    for (int i = 0; i<q; ++i) {
        if (ans[i] != -2) {
            cout<<max(0,i-ans[i])<<endl;
        }
    }
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5037 ms 16320 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1536 KB Output is correct
2 Correct 4 ms 1664 KB Output is correct
3 Correct 11 ms 1664 KB Output is correct
4 Correct 35 ms 1664 KB Output is correct
5 Correct 269 ms 20844 KB Output is correct
6 Execution timed out 5071 ms 21256 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1704 KB Output is correct
2 Incorrect 32 ms 1664 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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