QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#155543#1272. Dynamic Convex HullshjeongWA 348ms97564kbC++145.2kb2023-09-01 19:29:512023-09-01 19:29:51

Judging History

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

  • [2023-09-01 19:29:51]
  • 评测
  • 测评结果:WA
  • 用时:348ms
  • 内存:97564kb
  • [2023-09-01 19:29:51]
  • 提交

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'