QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#358865 | #112. Bulldozer | Dimash | 0 | 3ms | 4004kb | C++20 | 4.4kb | 2024-03-20 03:13:19 | 2024-03-20 03:13:21 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4e5+ 5, MOD = 998244353;
#define int ll
int n,pos[N],t[N];
ll x[N],y[N],w[N];
vector<array<ll,3>> a;
struct node{
ll res,mxl,mxr,sum;
};
node T[N * 4];
node merge(node l,node r){
node ret;
ret.sum = l.sum + r.sum;
ret.res = max({l.res,r.res});
ret.res = max(ret.res,l.mxr + r.mxl);
ret.mxr = max(r.mxr,r.sum + l.mxr);
ret.mxl = max(l.mxl,l.sum + r.mxl);
return ret;
}
void upd(int pos,ll val,int v = 1,int tl = 1,int tr = n){
if(tl == tr){
T[v].sum = val;
T[v].res = T[v].mxr = T[v].mxl = max(0ll,val);
}else{
int tm = (tl + tr) >> 1;
if(pos <= tm) upd(pos,val,v+v,tl,tm);
else upd(pos,val,v+v+1,tm+1,tr);
T[v] = merge(T[v+v],T[v+v+1]);
}
}
void out(int v = 1,int tl = 1,int tr = n){
if(tl == tr){
cout << tl << ' ' << T[v].sum << '\n';
}else{
int tm = (tl + tr) >> 1;
out(v+v,tl,tm);
out(v+v+1,tm+1,tr);
}
}
void test() {
cin >> n;
for(int i = 1;i <= n;i++){
cin >> x[i] >> y[i] >> w[i];
}
if(n == 1){
cout << max(0ll,w[1]) << '\n';
return;
}
vector<pair<long double,pair<int,int>>> cur;
for(int i = 1;i <= n;i++){
for(int j = i+1;j <= n;j++){
long double val;
if(x[i] == x[j]) val = 2e9;
else val = (long double)(y[j]-y[i]) / (long double)(x[j] - x[i]);
cur.push_back({val,{i,j}});
}
}
ll res = 0;
sort(cur.rbegin(),cur.rend());
int ii = cur[0].second.first,jj = cur[0].second.second;
for(int i = n;i >= 1;i--){
if(x[ii] == x[jj]){
a.push_back({x[i],y[i],i});
}else{
a.push_back({x[i],-y[i],i});
}
}
sort(a.begin(),a.end());
for(int i = 0;i < (int)a.size();i++){
pos[a[i][2]] = i + 1;
t[i + 1] = a[i][2];
upd(i+1,w[a[i][2]]);
}
for(int i = 0;i < (int)cur.size();i++){
// for(int j = 1;j <= n;j++){
// cout << t[j] << ' ';
// }
// cout << '\n';
vector<pair<int,int>> ss,s1;
for(int j = i;j <= (int)cur.size();j++){
if(j == (int)cur.size() || cur[j].first != cur[i].first){
i = j - 1;
break;
}
int L = min(pos[cur[j].second.first], pos[cur[j].second.second]), R = max(pos[cur[j].second.first],
pos[cur[j].second.second]);
ss.push_back({L,R});
}
vector<ll> sums;
sort(ss.begin(),ss.end());
ll mn = 0,curs = 0;
ll max_checked;
for(int j = 0;j < (int)ss.size();j++) {
if (j && max_checked >= ss[j].second) continue;
int mx = ss[j].second;
for (int k = j; k <= (int) ss.size(); k++) {
if (k == (int) ss.size() || ss[k].first != ss[j].first) {
j = k - 1;
break;
}
max_checked = ss[k].second;
mx = ss[k].second;
}
int l = ss[j].first, r = mx;
s1.push_back({l, r});
// cout << l << ' ' << r << '\n';
while (l < r) {
swap(t[l], t[r]);
upd(l, w[t[l]]);
upd(r, w[t[r]]);
pos[t[l]] = l;
pos[t[r]] = r;
l++;
r--;
}
}
// cout << T[1].res << "x\n";
// cout << '\n';
// for(int j = 1;j <= n;j++){
// cout << j << ' ' << w[t[j]] << '\n';
// }
// cout << '\n';
for(auto [L,R]:s1){
ll f = w[t[L]];
// cout << L << ' ' << R << "x\n";
for(int j = L + 1;j <= R;j++){
upd(j,0);
f += w[t[j]];
}
upd(L,f);
}
// cout << '\n';
// out();
// cout << T[1].res << '\n';
res = max(res,T[1].res);
for(auto [L,R]:s1){
for(int j = L;j <= R;j++){
upd(j,w[t[j]]);
}
}
}
cout << res << '\n';
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);
int T = 1;
// cin >> T;
while(T--){
test();
}
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 4004kb
input:
100 547397735 0 -701876985 -994704489 0 -137482041 657756917 0 134137206 902929348 0 848664068 -942595218 0 905496420 -885718358 0 -183102425 -133322590 0 -765735957 40517489 0 137314145 -651698207 0 -755087111 -995622477 0 -437346891 905467861 0 -331241604 119881570 0 -555661137 -489890101 0 554937...
output:
0
result:
wrong answer 1st lines differ - expected: '3177735978', found: '0'
Subtask #2:
score: 0
Wrong Answer
Test #16:
score: 20
Accepted
time: 0ms
memory: 3792kb
input:
100 -24309550 482269965 -297648951 253448360 -441723643 -920713212 324597788 390083514 -865804754 713394653 -881475679 678850273 -445282104 369972896 691296843 69042891 -867513631 -239602542 -391732493 330791482 17449017 279658315 890578483 565738698 625283527 15481214 530839875 592822547 33796172 4...
output:
8062662362
result:
ok single line: '8062662362'
Test #17:
score: 0
Accepted
time: 3ms
memory: 3784kb
input:
100 -257587011 400852223 -220309345 -875500067 -86782621 326270594 -414287853 -977479920 -984533791 -635666918 -708630100 326066280 -615040019 -993541890 -685301992 -760310577 221302942 45160524 -990846996 351043755 -648825880 -918729931 -379977547 911808427 252530998 107120801 -919405596 507878869 ...
output:
7374350612
result:
ok single line: '7374350612'
Test #18:
score: 0
Accepted
time: 2ms
memory: 3836kb
input:
100 -234721699 646933168 -338655575 -806569531 -71216264 -872209889 740102166 -655865625 80137029 -619042650 86451086 919481887 -613310459 862325871 299940063 -486792319 385052870 -459562867 -877904368 -297131478 447851188 199060395 -82554072 -131371354 -952281361 -710915129 307615240 -507291693 907...
output:
6210932418
result:
ok single line: '6210932418'
Test #19:
score: 0
Accepted
time: 2ms
memory: 3812kb
input:
100 -573155230 -21482599 137188437 -858318223 -627279123 74329590 -17310327 -177777278 788416416 -670979585 820505465 -787614633 562566093 273531226 733397305 -64307790 599053244 -297009699 817165433 -369316382 924081906 720802586 596624938 351428871 115928798 523348194 -586662700 -885459046 -895204...
output:
8054120128
result:
ok single line: '8054120128'
Test #20:
score: 0
Accepted
time: 3ms
memory: 3768kb
input:
100 701468719 174754273 994891446 508373256 -732987695 648967734 369948378 -700859918 834543102 -862822283 -588546632 -394089051 -880849099 -911153118 -293420654 861677968 917107626 824561386 -359587638 -857777409 -913592764 -135640113 -867460034 933004325 -971454790 -711909514 -274071917 953354587 ...
output:
11634325865
result:
ok single line: '11634325865'
Test #21:
score: 0
Accepted
time: 2ms
memory: 3768kb
input:
100 -406079738 55160150 -920565361 725055282 878590579 -800311783 -670162535 901392505 240442550 179342318 -384964487 -877645265 592925162 -971845016 -313276130 -659126723 30771322 771426239 -749159311 433142945 -927853693 -676435064 -378708256 -634922247 -486642852 229623957 530273029 -269137808 57...
output:
5685526749
result:
ok single line: '5685526749'
Test #22:
score: 0
Accepted
time: 2ms
memory: 3756kb
input:
100 -689190423 220983861 913342760 -807787476 31872295 443021122 -815582432 -456178077 894438019 326141220 -885526038 -427240265 390679145 408965343 -859292305 -928486438 685567377 248489199 -45211459 -700556605 17089679 -28845394 -9042916 -609052379 -469176499 481816321 -964805208 -918568308 448434...
output:
5621356954
result:
ok single line: '5621356954'
Test #23:
score: 0
Accepted
time: 2ms
memory: 3704kb
input:
100 187164857 900233795 990568533 -125876794 892832559 -940816798 -321878196 394069566 -244480066 -670273914 544753218 376169540 910151452 -861989228 -628283308 352749124 -819374074 741277319 -344455996 -217000212 -944332393 93217857 -174981978 -180151861 94543655 256400293 -888939691 782508726 -969...
output:
5036576367
result:
ok single line: '5036576367'
Test #24:
score: 0
Accepted
time: 2ms
memory: 3724kb
input:
100 531363827 -977931429 -76627691 566440726 -235229527 337777732 89516229 -489823739 -691867132 907305820 -945880242 -285222604 -183193668 -54409760 574440897 985173840 -947464549 358402992 38982981 -262700773 -810245538 193675330 -701123831 627792386 738870352 -634028033 -781105055 187273959 -5919...
output:
6460320517
result:
ok single line: '6460320517'
Test #25:
score: 0
Accepted
time: 2ms
memory: 3704kb
input:
100 -353174997 -351995784 -310183082 654678384 947350572 758744270 37126054 247124163 -388016820 282286988 -992350460 -723589942 531405766 108105766 52078769 -344987066 557794460 305053304 787276939 -576929156 212556717 34490507 -937159146 -794206787 368163585 -217235651 952032589 11623915 -65802595...
output:
8695946466
result:
ok single line: '8695946466'
Test #26:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
1 0 0 -1
output:
0
result:
ok single line: '0'
Test #27:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
1 0 0 1
output:
1
result:
ok single line: '1'
Test #28:
score: -20
Wrong Answer
time: 0ms
memory: 3584kb
input:
2 0 0 1 0 1 -1
output:
0
result:
wrong answer 1st lines differ - expected: '1', found: '0'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%