| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 985594 |
2024-05-18T09:24:45 Z |
Whisper |
Fish 3 (JOI24_fish3) |
C++17 |
|
358 ms |
66232 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define For(i, a, b) for (int i = (a); i <= (b); i++)
#define Ford(i, a, b) for (int i = (b); i >= (a); i --)
#define Rep(i, n) for (int i = 0; i < (n); ++i)
#define Repd(i, n) for (int i = (n) - 1; i >= 0; --i)
#define overload(_1, _2, _3, NAME, ...) NAME
#define FOR(...) overload(__VA_ARGS__, For, Rep)(__VA_ARGS__)
#define FORD(...) overload(__VA_ARGS__, Ford, Repd)(__VA_ARGS__)
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void setupIO(){
#define name "Whisper"
//Phu Trong from Nguyen Tat Thanh High School for gifted student
srand(time(NULL));
cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
//freopen(name".inp", "r", stdin);
//freopen(name".out", "w", stdout);
cout << fixed << setprecision(10);
}
template <class X, class Y>
bool minimize(X &x, const Y &y){
X eps = 1e-9;
if (x > y + eps) {x = y; return 1;}
return 0;
}
template <class X, class Y>
bool maximize(X &x, const Y &y){
X eps = 1e-9;
if (x + eps < y) {x = y; return 1;}
return 0;
}
#define MAX 300005
int numFish, numQuery, d;
int expect[MAX];
vector<pair<int, int>> event[MAX];
struct Node{
int mx, sum, sz;
Node(){
mx = -1, sum = 0, sz = 0;
}
Node(int _mx, int _sum, int _sz): mx(_mx), sum(_sum), sz(_sz){}
friend Node operator + (const Node& a, const Node& b){
Node res;
res.mx = max(a.mx, b.mx);
res.sum = a.sum + b.sum;
res.sz = a.sz + b.sz;
return res;
}
};
struct SegmentTree{
int n;
vector<Node> st;
vector<int> lz;
SegmentTree(){}
SegmentTree(int _n = 0){
this -> n = _n;
st.resize((n << 2));
lz.resize((n << 2));
}
void pushDown(int id, int l, int r){
if (!lz[id]) return ;
int m = (l + r) >> 1;
st[id << 1].sum = (m - l + 1) * lz[id];
st[id << 1].mx = lz[id];
st[id << 1 | 1].sum = (r - m) * lz[id];
st[id << 1 | 1].mx = lz[id];
lz[id << 1] = lz[id];
lz[id << 1 | 1] = lz[id];
lz[id] = 0;
}
void build(int id, int l, int r){
if (l == r){
st[id].sz = 1;
return;
}
int m = (l + r) >> 1;
build(id << 1, l, m);
build(id << 1 | 1, m + 1, r);
st[id] = st[id << 1] + st[id << 1 | 1];
}
void Modify(int id, int l, int r, int u, int v, int val){
if (u > r || v < l) return;
if (u <= l && v >= r) {
st[id].sum = (r - l + 1) * val;
st[id].mx = val;
return;
}
int m = (l + r) >> 1;
pushDown(id, l, r);
Modify(id << 1, l, m, u, v, val);
Modify(id << 1 | 1, m + 1, r, u, v, val);
st[id] = st[id << 1] + st[id << 1 | 1];
}
int Query(int id, int l, int r, int u, int v){
if (u > r || v < l) return 0;
if (u <= l && v >= r) return st[id].sum;
int m = (l + r) >> 1;
int ql = Query(id << 1, l, m, u, v);
int qr = Query(id << 1 | 1, m + 1, r, u, v);
return (ql + qr);
}
int find(int id, int l, int r, int u, int v, int x){
if (u > r || v < l) return -1;
if (l == r && st[id].mx > x) return l;
else if (l == r) return -1;
int m = (l + r) >> 1;
int ans = -1;
if (st[id << 1].mx > x) ans = find(id << 1, l, m, u, v, x);
if (ans == -1) ans = find(id << 1 | 1, m + 1, r, u, v, x);
return ans;
}
};
int need[MAX], dis[MAX], A[MAX];
int ans[MAX];
void Whisper(){
cin >> numFish >> d;
for (int i = 1; i <= numFish; ++i) cin >> expect[i], need[i] = expect[i];
for (int i = numFish - 1; i >= 1; --i){
if (need[i] > need[i + 1]){
int diff = expect[i] - expect[i + 1];
diff = (diff + d - 1) / d;
A[i] += diff;
need[i] -= d * diff;
dis[i] = diff;
}
}
// FOR(i, 1, numFish) cout << need[i] << " ";
for (int i = 1; i <= numFish; ++i) A[i] += A[i - 1];
SegmentTree st(numFish + 1);
st.build(1, 1, numFish);
cin >> numQuery;
for (int i = 1; i <= numQuery; ++i){
int l, r; cin >> l >> r;
event[r].emplace_back(l, i);
}
for (int r = 1; r <= numFish; ++r){
if (r > 1){
int id = st.find(1, 1, numFish, 1, r - 1, dis[r]);
if (id == -1) id = r;
if (id <= r)
st.Modify(1, 1, numFish, id, r, dis[r]);
}
else{
st.Modify(1, 1, numFish, 1, 1, dis[1]);
}
for (pair<int, int>&x : event[r]){
int l = x.first, id = x.second;
int num = st.Query(1, 1, numFish, l, l);
if(need[l] + d * num < 0) ans[id] = -1;
else{
ans[id] = A[r] - A[l - 1] - st.Query(1, 1, numFish, l, r);
}
}
}
for (int i = 1; i <= numQuery; ++i) cout << ans[i] << "\n";
}
signed main(){
setupIO();
int Test = 1;
// cin >> Test;
for ( int i = 1 ; i <= Test ; i++ ){
Whisper();
if (i < Test) cout << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 2 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
14684 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
358 ms |
66232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
108 ms |
29884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
291 ms |
58448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 2 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
14684 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
