oj.uz

답안 #418980

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
418980 2021-06-06T09:39:46 Z usachevd0 식물 비교 (IOI20_plants) C++17
11 / 100
 167 ms 3028 KB 
#include <bits/stdc++.h>
#ifndef LOCAL
    #include "plants.h"
#endif

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define Time (clock() * 1.0 / CLOCKS_PER_SEC)
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
    return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
    return y > x ? (x = y, true) : false;
}
void debug_out() {
    cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
    cerr << ' ' << A;
    debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
    for (int i = 0; i < n; ++i)
        cerr << a[i] << ' ';
    cerr << endl;
}
#ifdef LOCAL
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
    #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
    #define debug(...) 1337
    #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
    for (auto& e : v)
        stream << e << ' ';
    return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << ' ' << p.second;
}

namespace sol {
    const int INF32 = 1e9;
    const int maxN = 3e2 + 5;
    int n, k;
    int r[maxN];
    
    int prior[maxN];
    bool earlier[maxN][maxN];

    int md(int i) {
        return (i % n + n) % n;
    }

    bool in_seg(int x, int l, int r) {
        if (l <= r)
            return l <= x && x <= r;
        return x >= l || x <= r;
    }
    
    namespace sgt {
        const int logN = 9;
        const int N = 1 << logN;
        int mn[2][2 * N];
        int lazy[2][2 * N];
        
        void apply(int v, int delta0, int delta1) {
            mn[0][v] += delta0;
            lazy[0][v] += delta0;
            mn[1][v] += delta1;
            lazy[1][v] += delta1;
        }
        void push(int v) {
            // if (!lazy[0][v] && !lazy[1][v]) return;
            apply(v << 1, lazy[0][v], lazy[1][v]);
            apply(v << 1 | 1, lazy[0][v], lazy[1][v]);
            lazy[0][v] = lazy[1][v] = 0;
        }
        void upd(int v) {
            for (int t = 0; t < 2; ++t)
                mn[t][v] = min(mn[t][v << 1], mn[t][v << 1 | 1]);
        }
        
        void build(int v, int vl, int vr) {
            lazy[0][v] = lazy[1][v] = 0;
            if (vl == vr) {
                mn[0][v] = mn[1][v] = r[vl];
                return;
            }
            int vm = (vl + vr) >> 1;
            build(v << 1, vl, vm);
            build(v << 1 | 1, vm + 1, vr);
            upd(v);
        }
        
        void add(int v, int vl, int vr, int l, int r, int delta0, int delta1) {
            if (l > r || vr < l || r < vl) return;
            if (l <= vl && vr <= r) {
                apply(v, delta0, delta1);
                return;
            }
            int vm = (vl + vr) >> 1;
            push(v);
            add(v << 1, vl, vm, l, r, delta0, delta1);
            add(v << 1 | 1, vm + 1, vr, l, r, delta0, delta1);
            upd(v);
        }
        
        void disable(int v, int vl, int vr, int i, int t) {
            if (vl == vr) {
                mn[t][v] = +INF32;
                return;
            }
            int vm = (vl + vr) >> 1;
            push(v);
            if (i <= vm)
                disable(v << 1, vl, vm, i, t);
            else
                disable(v << 1 | 1, vm + 1, vr, i, t);
            upd(v);
        }
        
        int getFirstZero(int v, int vl, int vr, int t) {
            // debug(v, vl, vr, t, mn[t][v]);
            if (mn[t][v] > 0) return -1;
            if (vl == vr) return vl;
            int vm = (vl + vr) >> 1;
            push(v);
            if (mn[t][v << 1] == 0)
                return getFirstZero(v << 1, vl, vm, t);
            return getFirstZero(v << 1 | 1, vm + 1, vr, t);
        }
        
        int gt(int v, int vl, int vr, int i, int t) {
            if (vl == vr) return mn[t][v];
            int vm = (vl + vr) >> 1;
            push(v);
            if (i <= vm)
                return gt(v << 1, vl, vm, i, t);
            return gt(v << 1 | 1, vm + 1, vr, i, t);
        }
        int gt(int i, int t) {
            return gt(1, 0, n - 1, i, t);
        }
        
        void add(int l, int r, int delta0, int delta1) {
            // cerr << "add " << l << ' ' << r << ' ' << delta0 << ' ' << delta1 << endl;
            if (l <= r)
                add(1, 0, n - 1, l, r, delta0, delta1);
            else {
                add(1, 0, n - 1, 0, r, delta0, delta1);
                add(1, 0, n - 1, l, n - 1, delta0, delta1);
            }
        }
    }
}

void dbg() {
    using namespace sol;
    for (int t = 0; t < 2; ++t) {
        cerr << t << ":   ";
        for (int i = 0; i < n; ++i)
            cerr << sgt::gt(i, t) << ' ';
        cerr << endl;
    }
}

void init(int _k, vector<int> _r) {
    using namespace sol;
    n = _r.size();
    if (n > 300) exit(0);
    k = _k;
    for (int i = 0; i < n; ++i) 
        r[i] = _r[i];
    
    
    for (int x = 0; x < n; ++x) {
        sgt::build(1, 0, n - 1);
        for (int i = 0; i < n; ++i)
            if (r[i] == 0) {
                sgt::add(md(i + 1), md(i + k - 1), 0, +1);
                sgt::disable(1, 0, n - 1, i, 0);
            }
        sgt::add(x, x, 0, +1);
        for (int y = 0; y < n; ++y) {
            int i = sgt::getFirstZero(1, 0, n - 1, 1);
            if (i == -1) {
                break;
            }
            // prior[i] = y;
            earlier[i][x] = 1;
            sgt::disable(1, 0, n - 1, i, 0);
            sgt::disable(1, 0, n - 1, i, 1);
            sgt::add(md(i + 1), md(i + k - 1), 0, -1);
            sgt::add(md(i - k + 1), md(i - 1), -1, -1);
            for (int j = sgt::getFirstZero(1, 0, n - 1, 0); j != -1; j = sgt::getFirstZero(1, 0, n - 1, 0)) {
                sgt::add(md(j + 1), md(j + k - 1), 0, +1);
                sgt::disable(1, 0, n - 1, j, 0);
            }
        }
        // for (int i = 0; i < n; ++i)
        //     priorx[x][i] = prior[i];
    }
}

int compare_plants(int x, int y) {
    using namespace sol;
    
    
    bool good[2] = {0, 0};
    for (int rot = 0; rot < 2; ++rot, swap(x, y)) {
        good[rot] = earlier[x][y];
    }
    
    if (good[0] && good[1])
        return 0;
    if (good[0])
        return +1;
    return -1;
}


#ifdef LOCAL

static int n, k, q;
static std::vector<int> r;
static std:: vector<int> x;
static std:: vector<int> y;
static std:: vector<int> answer;
int main() {
    freopen("in", "r", stdin);
    assert(scanf("%d%d%d", &n, &k, &q) == 3);
    r.resize(n);
    answer.resize(q);
    for (int i = 0; i < n; i++) {
        int value;
        assert(scanf("%d", &value) == 1);
        r[i] = value;
    }
    x.resize(q);
    y.resize(q);
    for (int i = 0; i < q; i++) {
        assert(scanf("%d%d", &x[i], &y[i]) == 2);
    }
    fclose(stdin);

    init(k, r);
    for (int i = 0; i < q; i++) {
        answer[i] = compare_plants(x[i], y[i]);
    }

    for (int i = 0; i < q; i++) {
        printf("%d\n", answer[i]);
    }

    fclose(stdout);

    return 0;
}


// int32_t main() {
//     #ifdef LOCAL
//         freopen("in", "r", stdin);
//     #endif
//     ios::sync_with_stdio(0);
//     cin.tie(0);
    
    
    
    
//     return 0;
// }
#endif

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 57 ms 3028 KB Output is correct
7 Incorrect 44 ms 2728 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 9 ms 348 KB Output is correct
6 Incorrect 1 ms 332 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 9 ms 348 KB Output is correct
6 Incorrect 1 ms 332 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 38 ms 2636 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 2 ms 204 KB Output is correct
6 Correct 15 ms 400 KB Output is correct
7 Correct 167 ms 920 KB Output is correct
8 Correct 114 ms 1332 KB Output is correct
9 Correct 123 ms 1244 KB Output is correct
10 Correct 116 ms 1240 KB Output is correct
11 Correct 155 ms 1252 KB Output is correct
12 Correct 132 ms 1240 KB Output is correct
13 Correct 119 ms 1348 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Incorrect 1 ms 204 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 57 ms 3028 KB Output is correct
7 Incorrect 44 ms 2728 KB Output isn't correct
8 Halted 0 ms 0 KB -