QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#155545 | #1272. Dynamic Convex Hull | shjeong | AC ✓ | 554ms | 129168kb | C++14 | 5.4kb | 2023-09-01 19:32:52 | 2023-09-01 19:32:53 |
Judging History
answer
#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
typedef __int128_t ll;
typedef long long LL;
const ll inf = 9e18;
LL n, m, q;
struct Line{
ll a,b;
ll f(ll x){ return (x-a)*(x-a)*(x-a)*(x-a)+b; }
};
Line max(Line a, Line b, ll x){ return a.f(x) >= b.f(x) ? a : b;}
Line min(Line a, Line b, ll x){ return a.f(x) < b.f(x) ? a : b;}
ll cnt;
ll Q[101010];
bool chk[202020];
struct segtree{
struct lichao{
struct Node{
ll l,r,s,e;
Line line;
Node(ll L, ll R, ll S, ll E, Line LINE): l(L), r(R), s(S), e(E), line(LINE){}
};
vector<Node> tree;
stack<tuple<ll,ll,Node>> stk;
void upd(ll node, Line k, ll i){
if(tree.empty())tree.push_back({-1,-1,1,50000,{0,inf}});
ll s = tree[node].s, e = tree[node].e;
Line low = min(tree[node].line,k,s), high = max(tree[node].line,k,s);
if(low.f(e) <= high.f(e)){
auto next = tree[node];
next.line = low;
stk.push({node,i,tree[node]});
tree[node].line = low;
cnt++;
return;
}
ll mid = s+e>>1;
if(low.f(mid) <= high.f(mid)){
auto next = tree[node];
next.line = low;
cnt++;
stk.push({node,i,tree[node]});
if(next.r == -1){
next.r = tree.size();
cnt++;
auto NEXT = Node(-1,-1,mid+1,e,{0,inf});
tree.push_back(NEXT);
stk.push({-1,-1,Node(-1,-1,-1,-1,{0,inf})});
}
tree[node] = next;
upd(tree[node].r,high,i);
}
else{
auto next = tree[node];
next.line = high;
cnt++;
stk.push({node,i,tree[node]});
if(next.l == -1){
next.l = tree.size();
cnt++;
auto NEXT = Node(-1,-1,s,mid,{0,inf});
tree.push_back(NEXT);
stk.push({-1,-1,Node(-1,-1,-1,-1,{0,inf})});
}
tree[node] = next;
upd(tree[node].l,low,i);
}
}
void rollback(ll x){
while(x--){
auto [t,i,N] = stk.top();
stk.pop();
if(t==-1)tree.pop_back();
else tree[t] = N, chk[i]=0;
}
}
ll query(ll node, ll x){
if(node==-1)return inf;
ll s = tree[node].s, e = tree[node].e;
ll mid = s+e>>1;
if(x<=mid)return min(query(tree[node].l,x), tree[node].line.f(x));
return min(query(tree[node].r,x), tree[node].line.f(x));
}
} cht;
vector<vector<tuple<ll,ll,ll>>> tree;
segtree(): tree(808080){}
void upd(ll node, ll s, ll e, ll l, ll r, tuple<ll,ll,ll> diff){
if(e<l or r<s)return;
if(l<=s and e<=r){
tree[node].push_back(diff);
}
else{
ll mid = s+e>>1;
upd(node*2,s,mid,l,r,diff); upd(node*2+1,mid+1,e,l,r,diff);
}
}
void query(ll node, ll s, ll e){
ll ret = 0;
for(auto [i,a,b] : tree[node]){
cnt = 0;
if(!chk[i])chk[i]=1,cht.upd(0,{a,b},i), ret += cnt;
}
if(s==e){
LL res = (LL)cht.query(0,Q[s]);
cout<<(res==inf ? -1 : res)<<"\n";
}
else{
ll mid = s+e>>1;
query(node*2,s,mid);
query(node*2+1,mid+1,e);
}
cht.rollback(ret);
}
};
struct asdf{
ll a,b,s,e;
};
int main(){
fast;
LL t; cin>>t;
while(t--){
memset(chk,0,sizeof(chk));
memset(Q,0,sizeof(Q));
segtree seg;
m=0;
cin>>n>>q;
vector<asdf> v2(n+q+2);
vector<pair<ll,asdf>> v;
for(int i = 1 ; i <= n ; i++){
LL a,b; cin>>a>>b;
v2[i] = {a,b,m+1,-1};
}
ll cnt = n;
for(int i = 1 ; i <= q ; i++){
LL a,b,c; cin>>a>>b;
if(a==1){
cin>>c;
v2[++cnt] = {b,c,m+1,-1};
}
if(a==2){
v2[b].e = m;
v.push_back({b,v2[b]});
}
if(a==3){
Q[++m] = b;
}
}
for(int i = 1 ; i <= cnt ; i++){
if(v2[i].e<0){
v2[i].e = m;
v.push_back({i,v2[i]});
}
}
for(auto [i,_] : v){
auto [a,b,s,e] = _;
seg.upd(1,1,m,s,e,{i,a,b});
}
seg.query(1,1,m);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 5ms
memory: 23820kb
input:
1 2 8 3 9 6 100 3 4 2 1 3 4 1 1 1 3 4 2 2 2 3 3 4
output:
10 116 82 -1
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 554ms
memory: 129168kb
input:
5 100000 100000 39858 403048304064108142 6205 947055477496917683 788 911049878617783635 4261 626046370039242987 25008 685663359245704160 2202 848160200813297060 6216 289413959649340862 13189 722639235230562920 14820 749131972848517338 40221 716370580825502902 43025 222416883111096081 239 67541747335...
output:
105232514047244 112754306318445 54986177051691 74963972949549 118945174103964 69834459127665 33854058398778 275290771453117 65113537128811 45299248387930 51716327598553 68877950911521 135565157115804 288717635366668 10159612877616 161717641191962 161420883029513 72741135915164 109027638283771 179113...
result:
ok 355519 lines