이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
template <class T> bool minimize(T &a, T b) {if (a > b) {a = b; return true;} return false;}
template <class T> bool maximize(T &a, T b) {if (a < b) {a = b; return true;} return false;}
const int N = 4e5 + 1, LG = 5, mod = 1e9 + 7;
const ll INF = 1e18;
int up[N][LG];
map <ll, int> pos;
int n, m, Q;
struct creature{
int x, v;
};
creature a[N];
void inp(){
cin >> n;
m = 0;
for(int i = 1; i <= n; i++){
cin >> a[i].v;
a[i].x = i;
}
for(int i = n+1; i <= n+m; i++){
cin >> a[i].x >> a[i].v;
a[i].v*=-1;
}
cin >> Q;
}
bool cmp(creature a, creature b){
return a.x < b.x;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
inp();
vector<ll> v;
sort(a+1, a+1+n, cmp);
for(int i = 1; i <= N; i++){
v.push_back(i);
//cout << a[i].v << " ";
}
for (int j = 0; j < LG; j++)
for (int i = 0; i <= n; i++)
up[i][j] = n + 1;
pos[0] = 0; ll sum = 0;
for (int i = 1; i <= n; i++) {
sum += a[i].v;
if (pos.count(sum)) up[pos[sum]][0] = i;
pos[sum] = i;
}
for (int i = n - 1; i >= 0; i--) minimize(up[i][0], up[i + 1][0]);
for (int j = 1; j < LG; j++)
for (int i = 0; i <= n; i++) {
int pos = i;
for (int times = 0; times < 16; times++)
if (pos <= n) pos = up[pos][j - 1];
up[i][j] = pos;
}
int x, y;
while(Q--){
cin >> x >> y;
int l = lower_bound(v.begin(), v.end(), x) - v.begin()+1, r = upper_bound(v.begin(), v.end(), y)-v.begin();
int pos = l - 1, ans = 0, k = LG - 1;
while (k >= 0) {
if (up[pos][k] <= r) pos = up[pos][k], ans += (1 << (4 * k));
else k--;
}
cout << ans << "\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |