QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#155543 | #1272. Dynamic Convex Hull | shjeong | WA | 348ms | 97564kb | C++14 | 5.2kb | 2023-09-01 19:29:51 | 2023-09-01 19:29:51 |
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 long long ll;
const ll inf = 8e18;
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];
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,Node,Node>> stk;
void upd(ll node, Line k){
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,tree[node],next});
tree[node].line = low;
cnt++;
return;
}
ll mid = s+e>>1;
if(low.f(mid) <= high.f(mid)){
auto next = tree[node];
cnt++;
stk.push({node,tree[node],next});
next.line = low;
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,Node(-1,-1,-1,-1,{0,inf}),NEXT});
}
tree[node] = next;
upd(tree[node].r,high);
}
else{
auto next = tree[node];
cnt++;
stk.push({node,tree[node],next});
next.line = high;
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,Node(-1,-1,-1,-1,{0,inf}),NEXT});
}
tree[node] = next;
upd(tree[node].l,low);
}
}
void rollback(ll x){
while(x--){
auto [t,N1,N2] = stk.top();
stk.pop();
if(t==-1)tree.pop_back();
else tree[t] = N1;
}
}
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<pair<ll,ll>>> tree;
segtree(): tree(808080){}
void upd(ll node, ll s, ll e, ll l, ll r, pair<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 [a,b] : tree[node]){
cnt = 0;
cht.upd(0,{a,b});
ret += cnt;
}
if(s==e){
ll res = 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(Q,0,sizeof(Q));
segtree seg;
m=0;
cin>>n>>q;
vector<asdf> v, v2(n+q+2);
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(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(v2[i]);
}
}
for(auto [a,b,s,e] : v)seg.upd(1,1,m,s,e,{a,b});
seg.query(1,1,m);
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 6ms
memory: 22960kb
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: -100
Wrong Answer
time: 348ms
memory: 97564kb
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 -8092942028225616895 275290771453117 65113537128811 45299248387930 -7907671611483219440 68877950911521 135565157115804 288717635366668 -8843428311051796480 161717641191962 161420883029513 72741135915164 1090...
result:
wrong answer 7th lines differ - expected: '33854058398778', found: '-8092942028225616895'