oj.uz

Submission #418915

# Submission time Handle Problem Language Result Execution time Memory
418915 2021-06-06T08:27:11 Z usachevd0 Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 5212 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 = 2e5 + 5;
    int n, k;
    int r[maxN];
    
    int rem[maxN];
    int f[maxN];
    int prior[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 = 18;
        const int N = 1 << logN;
        int mn[2 * N];
        int lazy[2 * N];
        
        void apply(int v, int delta) {
            mn[v] += delta;
            lazy[v] += delta;
        }
        void push(int v) {
            if (!lazy[v]) return;
            apply(v << 1, lazy[v]);
            apply(v << 1 | 1, lazy[v]);
            lazy[v] = 0;
        }
        void upd(int v) {
            mn[v] = min(mn[v << 1], mn[v << 1 | 1]);
        }
        
        void build(int v, int vl, int vr) {
            if (vl == vr) {
                mn[v] = rem[v];
                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 delta) {
            if (l > r || vr < l || r < vl || !delta) return;
            if (l <= vl && vr <= r) {
                apply(v, delta);
                return;
            }
            int vm = (vl + vr) >> 1;
            push(v);
            add(v << 1, vl, vm, l, r, delta);
            add(v << 1 | 1, vm + 1, vr, l, r, delta);
            upd(v);
        }
        
        void disable(int v, int vl, int vr, int i) {
            if (vl == vr) {
                mn[v] = +INF32;
                return;
            }
            int vm = (vl + vr) >> 1;
            push(v);
            if (i <= vm)
                disable(v << 1, vl, vm, i);
            else
                disable(v << 1 | 1, vm + 1, vr, i);
            upd(v);
        }
        
        int getFirstZero(int v, int vl, int vr) {
            if (mn[v] > 0) return -1;
            if (vl == vr) return vl;
            int vm = (vl + vr) >> 1;
            push(v);
            if (mn[v << 1] == 0)
                return getFirstZero(v << 1, vl, vm);
            return getFirstZero(v << 1 | 1, vm + 1, vr);
        }
    }
}

void init(int _k, vector<int> _r) {
    using namespace sol;
    n = _r.size();
    k = _k;
    for (int i = 0; i < n; ++i) 
        r[i] = _r[i];
    
    for (int i = 0; i < n; ++i)
        f[i] = r[i];
    for (int i = 0; i < n; ++i)
        if (r[i] == 0)
            for (int j = 1; j < k; ++j)
                ++f[md(i + j)];
    // sgt::build(1, 0, n - 1);
    
    for (int y = 0; y < n; ++y) {
        // mdebug(f, n);
        assert(count(f, f + n, 0) == 1);
        int i = find(f, f + n, 0) - f;
        // debug(i);
        prior[i] = y;
        f[i] = +INF32;
        for (int j = 1; j < k; ++j) {
            --f[md(i + j)];
        }
        for (int j = 1; j < k; ++j) {
            int t = md(i - j);
            --f[t];
            if (--r[t] == 0) {
                for (int j = 1; j < k; ++j)
                    ++f[md(t + j)];
            }
        }
    }
}

int compare_plants(int x, int y) {
    using namespace sol;
    
    if (prior[x] < prior[y])
        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

# 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 0 ms 204 KB Output is correct
4 Runtime error 1 ms 460 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 29 ms 484 KB Output is correct
7 Correct 718 ms 5096 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 29 ms 436 KB Output is correct
10 Correct 720 ms 5048 KB Output is correct
11 Correct 483 ms 5188 KB Output is correct
12 Correct 484 ms 5196 KB Output is correct
13 Correct 889 ms 5212 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 29 ms 484 KB Output is correct
7 Correct 718 ms 5096 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 29 ms 436 KB Output is correct
10 Correct 720 ms 5048 KB Output is correct
11 Correct 483 ms 5188 KB Output is correct
12 Correct 484 ms 5196 KB Output is correct
13 Correct 889 ms 5212 KB Output is correct
14 Execution timed out 4050 ms 5160 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Runtime error 1 ms 460 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Runtime error 2 ms 460 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.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 0 ms 204 KB Output is correct
4 Runtime error 1 ms 460 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -