QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#358865#112. BulldozerDimash0 3ms4004kbC++204.4kb2024-03-20 03:13:192024-03-20 03:13:21

Judging History

This is the latest submission verdict.

  • [2024-03-20 03:13:21]
  • Judged
  • Verdict: 0
  • Time: 3ms
  • Memory: 4004kb
  • [2024-03-20 03:13:19]
  • Submitted

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%