QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#155545#1272. Dynamic Convex HullshjeongAC ✓554ms129168kbC++145.4kb2023-09-01 19:32:522023-09-01 19:32:53

Judging History

你现在查看的是最新测评结果

  • [2023-09-01 19:32:53]
  • 评测
  • 测评结果:AC
  • 用时:554ms
  • 内存:129168kb
  • [2023-09-01 19:32:52]
  • 提交

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