#910949 (C++17) No.2404 Vertical Throw Up

• 問題: No.2404 Vertical Throw Up
• ユーザー: kmjp
• 提出日時: 2023-09-05 00:06:54
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 2,092 bytes
• コンパイル時間: 1,705 ms
• コンパイル使用メモリ: 197,896 KB
• 最終ジャッジ日時: 2025-02-16 18:37:23
• ジャッジサーバーID （参考情報）: judge1 / judge5

ファイルパターン	結果
sample	AC * 1 WA * 2
other	WA * 30

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define FORR2(x,y,arr) for(auto& [x,y]:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
template<class T> bool chmax(T &a, const T &b) { if(a<b){a=b;return 1;}return 0;}
template<class T> bool chmin(T &a, const T &b) { if(a>b){a=b;return 1;}return 0;}
//-------------------------------------------------------
template<typename V> struct LeChaoTree {
    static const V inf=3LL<<60;
    const ll range=1<<30;
    const bool cmptype=1; //true:max false:min
    struct node {
        node(V a=0,V b=-inf) : A(a),B(b){ le=ri=NULL;}
        V val(ll x) { return A*x+B;}
        V A,B;  // Ax+B
        node *le, *ri;
    };
    
    node* root;
    LeChaoTree() { root=new node(0,-inf);}
    
    void add(node* n, V a,V b,ll L,ll R) {
        ll M=(L+R)/2;
        
        bool lef=(n->val(L) > a*L+b);
        bool mid=(n->val(M) > a*M+b);
        bool ri=(n->val(R) > a*R+b);
        
        if(lef&&ri) return;
        if(!lef&&(!ri || R-L==1)) {
            n->A=a;
            n->B=b;
            return;
        }
        
        if(R-L==1) return;
        if(!n->ri) n->ri=new node();
        if(!n->le) n->le=new node();
        add(n->ri,a,b,M,R);
        add(n->le,a,b,L,M);
    }
    
    void add(V a,V b) { 
        if(!cmptype) a=-a,b=-b;
        add(root,a,b,0,range);
    }
    
    V query(ll x) {
        V ret=-inf;
        node* cur=root;
        ll L=0, R=range;
        while(cur) {
            ret=max(ret,cur->val(x));
            ll m=(L+R)/2;
            if(x<m) cur=cur->le, R=m;
            else cur=cur->ri, L=m;
            
        }
        
        if(!cmptype) ret=-ret;
        return ret;
    }
};
LeChaoTree<ll> lct;
ll A;
ll Q;
void solve() {
    int i,j,k,l,r,x,y; string s;
    
    cin>>A>>Q;
    while(Q--) {
        ll P,Q;
        cin>>i;
        if(i==1) {
            cin>>P>>Q;
            lct.add((P+Q),-P*Q);
        }
        else {
            cin>>P;
            Q=A*max(0LL,lct.query(P))-A*P*P;
            cout<<Q<<endl;
        }
    }
}
int main(int argc,char** argv){
    string s;int i;
    if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
    FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
    cout.tie(0); solve(); return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX