oj.uz

Submission #547594

# Submission time Handle Problem Language Result Execution time Memory
547594 2022-04-11T03:31:48 Z flashhh Ancient Machine (JOI21_ancient_machine) C++17
0 / 100
 87 ms 15068 KB 
#include <bits/stdc++.h>
#include "Anna.h"

using namespace std;

void send(char x) {
    if (x == 'X') {
        Send(0);
        Send(0);
    }
    else if (x == 'Y') {
        Send(0);
        Send(1);
    }
    else {
        Send(1);
        Send(0);
    }
}

void Anna(int n,vector<char> s) {
    for (int i=0;i<n;++i) send(s[i]);
}

#include <bits/stdc++.h>
#include "Bruno.h"
#define N 100005
#define pii pair<int,int>
#define fi first
#define se second

using namespace std;

struct node {
    int idx,val,lazy;

    node() {}
    node(int idx1,int val1,int lazy1) {
        idx = idx1; val = val1; lazy = lazy1;
    }
};

int n,l;
char a[N];
node it[N<<2];
pii ma,b[N],dp[N];
bool dd[N],erased[N];
vector<int> s;

/*void Bruno(int &n,int &l,vector<int> &s) {
    cin >> n >> l;

    s.resize(l);
    for (int i=0;i<l;++i) cin >> s[i];
}

void Remove(int x) {
    erased[x] = 1;
    cout << "Remove " << x-1 <<'\n';
}*/

void down(int id) {
    int nho = it[id].lazy;

    it[id<<1].val = max(it[id<<1].val, nho); it[id<<1].lazy = max(it[id<<1].lazy, nho);
    it[id<<1|1].val = max(it[id<<1|1].val, nho); it[id<<1|1].lazy = max(it[id<<1|1].lazy, nho);

    it[id].lazy = 0;
}

void upd_it(int id,int l,int r,int u,int v,pii val) {
    if (u>r || v<l) return;
    if (u<=l && v>=r) {
        if (it[id].val < val.fi) {
            it[id].val = val.fi;
            it[id].idx = val.se;
        }
        it[id].lazy = max(it[id].lazy, val.fi);

        return;
    }

    int mid = (l + r) >> 1; down(id);
    upd_it(id<<1,l,mid,u,v,val); upd_it(id<<1|1,mid+1,r,u,v,val);

    it[id].val = max(it[id<<1].val, it[id<<1|1].val);
}

pii get_it(int id,int l,int r,int u,int v) {
    if (u>r || v<l) return {0,0};
    if (u<=l && v>=r) return {it[id].val,it[id].idx};

    int mid = (l + r) >> 1; down(id);
    return max(get_it(id<<1,l,mid,u,v), get_it(id<<1|1,mid+1,r,u,v));
}

void Bruno(int n1,int l1,vector<int> s1) {
    n = n1; l = l1; s = s1;

    for (int i=0;i<n;++i)
        if (s[i<<1] == 0) {
            if (s[i<<1|1] == 0) a[i+1] = 'X';
            else a[i+1] = 'Y';
        }
        else a[i+1] = 'Z';

    int last = -1;

    for (int i=1;i<=n;++i)
        if (a[i] == 'X') last = i;
    else if (a[i] == 'Y') b[i].fi = last;

    last = -1;

    for (int i=n;i>=1;--i)
        if (a[i] == 'Z') last = i;
    else if (a[i] == 'Y') b[i].se = last;

    for (int i=1;i<=n;++i) {
        if (a[i] != 'Y' || b[i].fi == -1 || b[i].se == -1) continue;
        int l = b[i].fi; int r = b[i].se;

        pii kq = get_it(1,1,n,1,l);
        dp[i] = {kq.fi+1, kq.se};

        kq = {kq.fi+1, i};
        upd_it(1,1,n,r+1,n,kq);

        ma = max(ma, kq);
    }

    if (ma.fi == 0) {
        for (int i=1;i<=n;++i) Remove(i);
    }
    else {
        while (ma.se > 0) {
            dd[ma.se] = 1;
            ma.se = dp[ma.se].se;
        }

        for (int i=1;i<=n;++i)
            if (dd[i]) {
                int l = b[i].fi; int r = b[i].se;
                for (int j=l+1;j<i;++j) {
                    erased[j] = 1;
                    Remove(j);
                }
                for (int j=i+1;j<r;++j) {
                    erased[j] = 1;
                    Remove(j);
                }

                erased[i] = 1;
                Remove(i);
            }

        for (int i=1;i<=n;++i)
            if (!erased[i]) Remove(i);
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 520 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 15068 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -