제출 #429074

#제출 시각아이디문제언어결과실행 시간메모리
429074ACmachine식물 비교 (IOI20_plants)C++17
27 / 100
566 ms16548 KiB
#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 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; void init(int k, std::vector<int> r) { n = r.size(); 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(pos[x] < pos[y]) return 1; else return -1; }

컴파일 시 표준 에러 (stderr) 메시지

plants.cpp: In constructor 'segtree::segtree(int, std::vector<std::array<int, 2> >&)':
plants.cpp:44: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]
   44 |             if(i < init.size())
      |                ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...