| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1030899 |
2024-07-22T11:38:16 Z |
Antekb |
Tower (JOI24_tower) |
C++17 |
|
201 ms |
14052 KB |
#include "bits/stdc++.h" /** keep-include */
using namespace std;
#define rep(i, b, e) for(int i = (b); i <= (e); i++)
#define per(i, b, e) for(int i = (e); i >= (b); i--)
#define FOR(i, b, e) rep(i, b, (e) - 1)
#define SZ(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
auto &operator<<(auto &o, pair<auto, auto> p) {
return o << "(" << p.st << ", " << p.nd << ")"; }
auto operator<<(auto &o, auto x)->decltype(end(x), o) {
o << "{"; int i=0; for(auto e: x) o << ", " + 2*!i++ << e;
return o << "}"; }
#ifdef LOCAL
#define deb(x...) cerr << "[" #x "]: ", [](auto...$) { \
((cerr << $ << "; "),...) << endl; }(x)
#else
#define deb(...)
#endif
using se=pair<pair<ll, ll>, ll>;
bool from_both_sides;
void insert(set<se> &S, ll l, ll r, ll c){
vector<se> todo;
auto it=S.lower_bound(se(mp(mp(l, 0), 0)));
if(it!=S.begin())it--;
while(it!=S.end() && it->st.st<=r){
todo.pb(*it);
it++;
}
for(auto i : todo){
ll L=i.st.st, R=i.st.nd, C=i.nd;
if(L>r || R<l)continue;
S.erase(i);
if(L<l){
S.insert(mp(mp(L, l-1), C));
}
if(R>r){
S.insert(mp(mp(r+1, R), C+max(0ll, r+1-L)));
}
}
S.insert(se(mp(l, r), c));
}
ll pytaj(set<se> &S, ll x, ll D){
auto it=S.lower_bound(mp(mp(x%D+1,0), 0));
deb(x, D);
if(it==S.begin())return x%D;
it--;
deb(x, D, *it);
if(x%D<=it->st.nd){
deb("a");
if(it->st.st==0 && from_both_sides){
it=S.end();
it--;
return x%D+D-it->st.st+1+it->nd;
}
return x%D-it->st.st+1+it->nd;
}
else return x%D;
}
void solve() {
int n, q;
cin>>n>>q;
ll A, B, D;
cin>>D>>A>>B;
vector<pair<ll ,ll>> seg;
for(int i=0; i<n; i++){
ll l, r;
cin>>l>>r;
r=max(r, D-1);
if(i==0){
seg.pb(mp(l, r));
}
else {
if(l<=seg.back().nd+1){
seg.back().nd=max(seg.back().nd, r);
}
else seg.pb(mp(l, r));
int t=lower_bound(all(seg), mp(r+2-D,0ll))-seg.begin();
t--;
if(t>=0){
seg.back().nd=max(seg.back().nd, seg[t].nd+D);
}
}
if(seg.back().nd-seg.back().st>=D-1)seg.back().nd=1e12;
deb(seg);
}
B-=A*D;
n=seg.size();
vector<pair<ll, int> > Q;
vector<ll> res(q);
for(int i=0; i<q; i++){
ll x;
cin>>x;
int t=lower_bound(all(seg), mp(x+1, 0ll))-seg.begin();
t--;
if(t>=0 && seg[t].nd>=x){
res[i]=-1;
continue;
}
Q.pb(mp(x, i));
res[i]=x*A;
}
if(B>0){
vector<ll> odp(n);
for(int i=0; i<n; i++){
int t=lower_bound(all(seg), mp(seg[i].nd+2-D,0ll))-seg.begin();
if(t==0)odp[i]=1;
else{
odp[i]=odp[t-1]+1;
}
}
for(auto &[x, id] : Q){
int t=lower_bound(all(seg), mp(x+1, 0ll))-seg.begin();
t--;
if(t>=0)res[id]+=B*odp[t];
}
}
else{
deb(A, B, D, Q);
set<se> S;
sort(all(Q));
reverse(all(Q));
seg.pb(mp(2e12, 2e12));
for(auto &[l, r] : seg){
while(Q.size() && Q.back().st<l){
ll x=Q.back().st;
int id=Q.back().nd;
Q.pop_back();
res[id]+=B*((x-pytaj(S, x, D))/D);
}
if(l>1e12){
break;
}
ll val=pytaj(S, l-1, D);
deb(l, r, val);
if(l/D==r/D){
insert(S, l%D, r%D, val);
if(l%D==0 || r%D==D-1)from_both_sides=0;
}
else{
insert(S, l%D, D-1, val);
insert(S, 0, r%D, val);
from_both_sides=1;
}
deb("S");
for(auto &i:S){
deb(i);
}
}
}
for(int i=0; i<q; i++){
cout<<res[i]<<"\n";
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int tt = 1;
// cin >> tt;
FOR(te, 0, tt) solve();
return 0;
}
Compilation message
Main.cpp:17:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
17 | auto &operator<<(auto &o, pair<auto, auto> p) {
| ^~~~
Main.cpp:17:32: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
17 | auto &operator<<(auto &o, pair<auto, auto> p) {
| ^~~~
Main.cpp:17:38: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
17 | auto &operator<<(auto &o, pair<auto, auto> p) {
| ^~~~
Main.cpp:19:17: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
19 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
| ^~~~
Main.cpp:19:26: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
19 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
| ^~~~
Main.cpp: In function 'void solve()':
Main.cpp:156:23: warning: unused variable 'i' [-Wunused-variable]
156 | for(auto &i:S){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
46 ms |
5708 KB |
Output is correct |
| 4 |
Incorrect |
45 ms |
5536 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
356 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
344 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
7892 KB |
Output is correct |
| 2 |
Correct |
48 ms |
6360 KB |
Output is correct |
| 3 |
Correct |
2 ms |
344 KB |
Output is correct |
| 4 |
Correct |
201 ms |
12452 KB |
Output is correct |
| 5 |
Correct |
167 ms |
11968 KB |
Output is correct |
| 6 |
Correct |
178 ms |
12480 KB |
Output is correct |
| 7 |
Correct |
165 ms |
13148 KB |
Output is correct |
| 8 |
Correct |
175 ms |
11196 KB |
Output is correct |
| 9 |
Correct |
172 ms |
14052 KB |
Output is correct |
| 10 |
Correct |
172 ms |
12560 KB |
Output is correct |
| 11 |
Correct |
175 ms |
12988 KB |
Output is correct |
| 12 |
Correct |
167 ms |
12480 KB |
Output is correct |
| 13 |
Correct |
183 ms |
13132 KB |
Output is correct |
| 14 |
Correct |
81 ms |
3668 KB |
Output is correct |
| 15 |
Correct |
71 ms |
3004 KB |
Output is correct |
| 16 |
Correct |
61 ms |
2768 KB |
Output is correct |
| 17 |
Correct |
162 ms |
13852 KB |
Output is correct |
| 18 |
Correct |
155 ms |
11200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
46 ms |
5708 KB |
Output is correct |
| 4 |
Incorrect |
45 ms |
5536 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
