oj.uz

Submission #255859

# Submission time Handle Problem Language Result Execution time Memory
255859 2020-08-02T02:07:03 Z balbit Street Lamps (APIO19_street_lamps) C++14
20 / 100
 536 ms 36400 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");
        if (!tol.v.empty())
            qq.push(tol);
        if (!tor.v.empty())
            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 1 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 Incorrect 213 ms 16036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1536 KB Output is correct
2 Correct 2 ms 1536 KB Output is correct
3 Correct 2 ms 1664 KB Output is correct
4 Correct 2 ms 1664 KB Output is correct
5 Correct 181 ms 7996 KB Output is correct
6 Correct 323 ms 15128 KB Output is correct
7 Correct 536 ms 26128 KB Output is correct
8 Correct 502 ms 36400 KB Output is correct
9 Correct 154 ms 21268 KB Output is correct
10 Correct 166 ms 23328 KB Output is correct
11 Correct 182 ms 22716 KB Output is correct
12 Correct 484 ms 33668 KB Output is correct
13 Correct 484 ms 36360 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1664 KB Output is correct
2 Incorrect 2 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 1 ms 1536 KB Output isn't correct
2 Halted 0 ms 0 KB -