Submission #429159

#	Time	Username	Problem	Language	Result	Execution time	Memory
429159		ACmachine	Comparing Plants (IOI20_plants)	C++17	32 / 100	563 ms	14660 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j); i >= (k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
typedef long long ll;
#define pb push_back
int subtask = 1;
const int INF = (int)1e9;
array<int, 2> nl = {INF, INF};
int on;
struct segtree{
    vector<array<int, 2>> tree;
    vector<int> lazy;
    int n;
    void push(int v){
        lazy[v << 1] += lazy[v];
        lazy[v << 1 | 1] += lazy[v];
        tree[v << 1][0] += lazy[v];
        tree[v << 1 | 1][0] += lazy[v];
        lazy[v] = 0;
    }
    array<int, 2> comb(array<int, 2> a, array<int, 2> b){
        if(a[0] == b[0]){
            if(a[1] < b[1])
                swap(a, b);
            if(a[1] - b[1] > (b[1] + on - a[1]))
                return a;
            else
                return b;
        }
        else{
            return min(a, b);
        }
    }
    segtree(){} 
    segtree(int sz, vector<array<int, 2>> &init){
        n = 1;
        while(n < sz) n *= 2;
        tree.resize(2 * n, nl);
        lazy.resize(2 * n, 0);
        REP(i, n){
            if(i < init.size()) 
                tree[i + n] = init[i];
        }
        FORD(i, n - 1, 1, 1)
            tree[i] = comb(tree[i << 1], tree[i << 1 | 1]);
    }
    void upd(int l, int r, int val){ upd0(l, r, 0, n, 1, val); }
    void upd0(int l, int r, int beg, int end, int v,  int val){
        if(beg >= l && end <= r){
            tree[v][0] += val;
            lazy[v] += val;
            return;
        }
        if(beg >= r || end <= l)
            return;
        push(v);
        int mid = (beg + end) >> 1;
        upd0(l, r, beg, mid, v << 1, val);
        upd0(l, r, mid, end, v << 1 | 1, val);
        tree[v] = comb(tree[v << 1], tree[v << 1 | 1]);
    }
    array<int, 2> query(int l, int r){return query0(l, r, 0, n, 1); }
    array<int, 2> query0(int l, int r, int beg, int end, int v){
        if(beg >= l && end <= r)
            return tree[v];
        if(beg >= r || end <= l)
            return nl;
        push(v);
        int mid = (beg + end) >> 1;
        return comb(query0(l, r, beg, mid, v << 1),query0(l, r, mid, end, v << 1 | 1)); 
    }
};
segtree st;
int n;
vector<int> pos;
int k; 
vector<int> ps;
void init(int kk, std::vector<int> r) {
    k = kk; 
    n = r.size(); 
    if(kk == 2)
        subtask = 1;
    else
        subtask = 2;
    if(subtask == 1){
        ps.resize(n + 1, 0);
        REP(i, n){
            if(r[i] == 1){
                ps[i + 1] = -1;
            }
            else{
                ps[i + 1] = 1;
            }
            ps[i + 1] += ps[i];
        }
        return;
    }
    on = r.size();
    pos.resize(n, 0);
    
    vector<array<int, 2>> in(n);
    REP(i, n){
        in[i] = {r[i], i};
    }
	st = segtree(n, in);
    int curr = 0;
    REP(i, n){
        auto x = st.query(0, n);
        pos[x[1]] = curr++;
        st.upd(x[1], x[1] + 1, INF);
        int r = x[1];
        int l = x[1] - (k - 1);
        if(l >= 0){
            st.upd(l, r, -1);
        }
        else{
            st.upd(0, r, -1);
            l += n,
            st.upd(l, n, -1);
        }
    }
}

int compare_plants(int x, int y) {
    if(subtask == 1){
        x++; y++;
        bool swapped = false;
        if(x > y){
            swap(x, y);
            swapped = true;
        }
        int ans = 0;
        if(ps[y - 1] - ps[x - 1] == y - x){
            ans = 1;
        }
        else if(ps[y - 1] - ps[x - 1] == x - y){
            ans = -1;
        }
        int sum = ps[n] - ps[y - 1] + ps[x - 1];
        int dist = n - (y - x);
        if(sum == dist){
            ans = -1;
        }
        else if(sum == -dist){
            ans = 1;
        }
        if(swapped) ans *= -1;
        return ans;
    }
    if(pos[x] < pos[y])
        return 1;
    else
        return -1;	
}

Compilation message (stderr)

plants.cpp: In constructor 'segtree::segtree(int, std::vector<std::array<int, 2> >&)':
plants.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             if(i < init.size())
      |                ~~^~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25