#include <bits/stdc++.h>
// #define LOCAL
using namespace std;
const int NMAX = 200'001;
int n,k,q;
int r[NMAX];
int rpref[NMAX+1];
void init(int kl, vector<int> rl) {
n = rl.size();
k = kl;
for (int i = 0; i < n; ++i) {
r[i] = rl[i];
}
rpref[0] = 0;
for (int i = 1; i <= n; ++i) {
rpref[i] += rpref[i-1];
rpref[i] += r[i-1];
}
}
bool isSmaller(int x, int y) {
// Two conditions
// i) r[x] = ... = r[y-1] = 1
int s0 = rpref[y] - rpref[x];
if (s0 == (y-1-x+1)) return true;
// ii) r[y] = ... = r[n-1] = 1 and r[0] = ... = r[x-1] = 1
int s1 = rpref[n] - rpref[y+1];
s1 += rpref[x] - rpref[0];
if (s1 == 0) return true;
return false;
}
bool isGreater(int x, int y) {
// Two conditions
// i) r[x] = r[x+1] = ... = r[y-1] = 0
int s0 = rpref[y] - rpref[x];
if (s0 == 0) return true;
// ii) r[y] = ... = r[n-1] = 1 and r[0] = ... = r[x-1] = 1
int s1 = rpref[n] - rpref[y+1];
s1 += rpref[x] - rpref[0];
int l1 = (n-1-y);
l1 += x;
if (l1 == s1) return true;
return false;
}
// x, y: Labels of plants
// Return:
// 1: x taller than plant y
// -1: x smaller than plant y
// 0: inconclusive
int compare_plants(int x, int y) {
if (isGreater(x, y)) {
return 1;
} else if (isSmaller(x, y)) {
return -1;
} else {
return 0;
}
}
#ifdef LOCAL
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int nl, kl, ql;
cin >> nl >> kl >> ql;
vector<int> rl(nl);
for (auto& e : rl) cin >> e;
init(kl, rl);
for (int _ = 0; _ < ql; _++) {
int x, y;
cin >> x >> y;
cout << compare_plants(x, y);
if (_ < ql-1) cout << '\n';
}
return 0;
}
#endif
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |