結果
| 問題 |
No.2404 Vertical Throw Up
|
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2023-07-02 13:31:13 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 122 ms / 2,000 ms |
| コード長 | 5,424 bytes |
| コンパイル時間 | 2,117 ms |
| コンパイル使用メモリ | 186,420 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-09-14 06:49:10 |
| 合計ジャッジ時間 | 4,884 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 30 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
class cht {
private:
int size;
map<long long, long long> a_to_b;
map<long long, long long> a_to_x;
map<long long, long long> x_to_a;
long long xmax(long long a1, long long b1, long long a2, long long b2){
assert(a1<a2);
return (b1-b2)/(a2-a1);
}
bool need(long long a1, long long b1, long long a2, long long b2, long long a3, long long b3){
assert(a1<a2 && a2<a3);
return xmax(a1,b1,a2,b2)<xmax(a2,b2,a3,b3);
}
public:
cht(){
a_to_b[0]=LONG_LONG_MIN;
a_to_x[0]=LONG_LONG_MAX;
x_to_a[LONG_LONG_MAX]=0;
size=1;
}
void add(long long a, long long b){
auto it_first=a_to_b.begin();
auto it_last=a_to_b.end();
--it_last;
if(a_to_b.count(a)){
if(a_to_b[a]>b){
return;
} else {
a_to_b.erase(a);
x_to_a.erase(a_to_x[a]);
a_to_x.erase(a);
--size;
}
}
if(size==1){
a_to_x[0]=LONG_LONG_MIN;
x_to_a[LONG_LONG_MIN]=0;
a_to_b[a]=b;
a_to_x[a]=LONG_LONG_MAX;
x_to_a[LONG_LONG_MAX]=a;
++size;
return;
}
auto it_next=a_to_b.lower_bound(a);
if(it_next!=a_to_b.end()){
assert(it_next!=it_first);
auto it_prev=it_next;
--it_prev;
if(!need(it_prev->first, it_prev->second, a, b, it_next->first, it_next->second)){
return;
}
if(it_prev!=it_first){
x_to_a.erase(a_to_x[it_prev->first]);
a_to_x[it_prev->first]=xmax(it_prev->first, it_prev->second, a, b);
x_to_a[a_to_x[it_prev->first]]=it_prev->first;
}
a_to_b[a]=b;
a_to_x[a]=xmax(a, b, it_next->first, it_next->second);
x_to_a[a_to_x[a]]=a;
++size;
} else {
x_to_a.erase(a_to_x[it_last->first]);
a_to_x[it_last->first]=xmax(it_last->first, it_last->second, a, b);
x_to_a[a_to_x[it_last->first]]=it_last->first;
a_to_b[a]=b;
a_to_x[a]=LONG_LONG_MAX;
x_to_a[LONG_LONG_MAX]=a;
++size;
it_last=a_to_b.lower_bound(a);
}
auto it_n2=a_to_b.lower_bound(a);
if(it_n2!=it_last){
auto it_n1=it_n2;
++it_n2;
if(it_n2!=it_last){
auto it_n0=it_n1;
++it_n1;
++it_n2;
while(!need(it_n0->first, it_n0->second, it_n1->first, it_n1->second, it_n2->first, it_n2->second)){
auto it_tmp=it_n2;
x_to_a.erase(a_to_x[it_n0->first]);
x_to_a.erase(a_to_x[it_n2->first]);
a_to_x[it_n0->first]=xmax(it_n0->first, it_n0->second, it_n2->first, it_n2->second);
x_to_a.erase(a_to_x[it_n1->first]);
a_to_x.erase(it_n1->first);
a_to_b.erase(it_n1);
--size;
if(it_n2==it_last){
break;
} else {
it_n1=it_tmp;
++it_n2;
}
}
x_to_a[a_to_x[it_n0->first]]=it_n0->first;
x_to_a[a_to_x[it_n1->first]]=it_n1->first;
x_to_a[a_to_x[it_n2->first]]=it_n2->first;
}
}
auto it_p2=a_to_b.lower_bound(a);
if(it_p2!=it_first){
auto it_p1=it_p2;
--it_p2;
if(it_p2!=it_first){
auto it_p0=it_p1;
--it_p1;
--it_p2;
while(!need(it_p2->first, it_p2->second, it_p1->first, it_p1->second, it_p0->first, it_p0->second)){
auto it_tmp=it_p2;
x_to_a.erase(a_to_x[it_p2->first]);
x_to_a.erase(a_to_x[it_p0->first]);
a_to_x[it_p2->first]=xmax(it_p2->first, it_p2->second, it_p0->first, it_p0->second);
x_to_a.erase(a_to_x[it_p1->first]);
a_to_x.erase(it_p1->first);
a_to_b.erase(it_p1);
--size;
if(it_p2==it_first){
break;
} else {
it_p1=it_tmp;
--it_p2;
}
}
x_to_a[a_to_x[it_p2->first]]=it_p2->first;
x_to_a[a_to_x[it_p1->first]]=it_p1->first;
x_to_a[a_to_x[it_p0->first]]=it_p0->first;
}
}
}
long long max(long long x){
auto it=x_to_a.lower_bound(x);
return it->second*x+a_to_b[it->second];
}
};
int main(void)
{
int a;
cin >> a;
int q;
cin >> q;
cht l;
while(q--){
int e;
cin >> e;
if(e==1){
long long s,t;
cin >> s >> t;
l.add(a*(s+t),-a*s*t);
} else {
long long t;
cin >> t;
long long lmax=l.max(t);
if(lmax-a*t*t>0){
cout << lmax-a*t*t << endl;
} else {
cout << 0 << endl;
}
}
}
return 0;
}