QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#343213	#4253. Robot	ANIG	20	130ms	93656kb	C++14	2.7kb	2024-03-02 08:37:44	2024-03-02 08:37:45

Judging History

This is the latest submission verdict.

[2024-03-02 08:37:45]
Judged

Verdict: 20
Time: 130ms
Memory: 93656kb

Show

[2024-03-02 08:37:44]
Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+5,inf=1e18;
struct xd{
    int a,b;
    int f(int x){
        return a*x+b;
    }
};
struct node{
    int lson,rson;
    xd mx,mn;
}p[N*20];
int idx;
int news(){
    idx++;
    p[idx].mx=(xd){0,-inf};
    p[idx].mn=(xd){0,inf};
    return idx;
}
void init(int x){
    if(!p[x].lson)p[x].lson=news();
    if(!p[x].rson)p[x].rson=news();
}
void add1(int x,int l,int r,xd sm){
    int mid=l+r>>1;
    if(p[x].mx.f(mid)<sm.f(mid))swap(sm,p[x].mx);
    if(l==r)return;
    if(p[x].mx.f(l)>=sm.f(l)&&p[x].mx.f(r)>=sm.f(r))return;
    init(x);
    if(p[x].mx.f(l)>=sm.f(l))add1(p[x].rson,l,r,sm);
    else add1(p[x].lson,l,r,sm);
}
void add2(int x,int l,int r,xd sm){
    int mid=l+r>>1;
    if(p[x].mn.f(mid)>sm.f(mid))swap(sm,p[x].mn);
    if(l==r)return;
    if(p[x].mn.f(l)<=sm.f(l)&&p[x].mn.f(r)<=sm.f(r))return;
    init(x);
    if(p[x].mn.f(l)>=sm.f(l))add2(p[x].rson,l,r,sm);
    else add2(p[x].lson,l,r,sm);
}
void add(int x,int l,int r,xd sm,int nl,int nr){
    if(l<=nl&&r>=nr){
        add1(x,nl,nr,sm);
        add2(x,nl,nr,sm);
        return;
    }
    init(x);
    int mid=nl+nr>>1;
    if(l<=mid)add(p[x].lson,l,r,sm,nl,mid);
    if(r>mid)add(p[x].rson,l,r,sm,mid+1,nr);
}
int gets1(int x,int d,int nl,int nr){
    if(!x)return -inf;
    if(nl==nr)return p[x].mx.f(d);
    int mid=nl+nr>>1;
    if(d<=mid)return max(gets1(p[x].lson,d,nl,mid),p[x].mx.f(d));
    else return max(gets1(p[x].rson,d,mid+1,nr),p[x].mx.f(d));
}
int gets2(int x,int d,int nl,int nr){
    if(!x)return inf;
    if(nl==nr)return p[x].mn.f(d);
    int mid=nl+nr>>1;
    if(d<=mid)return min(gets2(p[x].lson,d,nl,mid),p[x].mn.f(d));
    else return min(gets2(p[x].rson,d,mid+1,nr),p[x].mn.f(d));
}
int n,m,w[N],nxt[N],op[N],k[N],ks[N],dy[N],fst[N],nw[N];
signed main(){
    int tm[N];
    memset(tm,0,sizeof(tm));
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    news();
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>w[i];
    for(int i=1;i<=m;i++)nxt[i]=m+1;
    tm[m+1]=1e9;
    for(int i=1;i<=m;i++){
        string s;
        cin>>tm[i]>>s;
        if(s[0]=='c'){
            cin>>k[i]>>ks[i];
            if(dy[k[i]])nxt[dy[k[i]]]=i,dy[k[i]]=i;
            else fst[k[i]]=i,dy[k[i]]=i;
        }else op[i]=1;
    }
    for(int i=1;i<=n;i++)add(1,0,tm[fst[i]],(xd){0,w[i]},0,1e9);
    memset(dy,0,sizeof(dy));
    for(int i=1;i<=m;i++){
        if(op[i]){
            cout<<max(gets1(1,tm[i],0,1e9),-gets2(1,tm[i],0,1e9))<<"\n";
        }else{
            w[k[i]]=w[k[i]]+nw[k[i]]*(tm[i]-tm[dy[k[i]]]);
            nw[k[i]]=ks[i];dy[k[i]]=i;
            add(1,tm[i],tm[nxt[i]],(xd){ks[i],w[k[i]]-ks[i]*tm[i]},0,1e9);
        }
    }
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0

Wrong Answer

time: 0ms

memory: 25716kb

input:

1999 2000
199 8854 -9513 9848 8434 -6615 -6770 4057 -9730 686 1586 6806 -511 -6328 -2250 2785 -4083 -3961 -711 9606 -9391 1041 -2844 -4889 993 -6955 -1982 -5300 9053 -5275 3950 -7977 -3652 8624 -716 -2013 -5229 -3686 -4602 -5031 9777 3802 491 -1354 -26 -3366 5285 5805 -7098 2233 -5967 -1318 -4553 63...

output:

86968438
360434523
838136414
913544563
969488608
1039885818
1109817781
1176515896
1251176599
1310476524
1510654766
1541254290
1558186230
1650869534
1683894444
1758250067
1785951331
1924000031
1993298953
2050165865
2254081337
2698178666
2750011758
2975976887
3216807039
3276625600
3332455240
335270492...

result:

wrong answer 358th numbers differ - expected: '33967293952', found: '33741085593'

Test #2:

score: 10

Accepted

time: 4ms

memory: 21624kb

input:

1999 2000
6817 4353 -8180 954 -2553 1768 4986 -889 7032 -450 1234 -7637 9636 380 3607 -2296 -4881 -9025 2375 -1561 -8807 -3103 4385 8883 -2887 -1185 1960 6711 3478 -1056 -1717 -534 -9885 -6301 6011 5965 -9833 -5181 5329 3688 -6837 9023 64 -8326 3021 -7193 -9218 -4699 2354 -4720 1621 7361 -5233 9211 ...

output:

result:

ok 994 numbers

Test #3:

score: 0

Wrong Answer

time: 130ms

memory: 80340kb

input:

99659 99039
-39276177 -64464963 -70081363 -443045475 -655771408 -409419920 -285052520 -312069074 -936205590 -10621715 -908116392 -660740279 -953732094 -591542519 -194540162 -139991296 -705911340 -778931920 -474438963 -518208970 -59960466 -981034014 -514533441 -217486555 -711871023 -615144144 -631291...

output:

result:

wrong answer 1st numbers differ - expected: '999962473', found: '999962407'

Test #4:

score: 0

Runtime Error

input:

99572 579859
-100705410 -669206879 -432488010 -384767624 -742351351 -839681487 -968882737 -976751481 57117493 -959321678 -819420190 -325014480 -636525861 -382469947 -876672604 -213012287 -209210199 -875230847 -920443172 -731589320 -946964322 -789362448 -872075805 -828546101 51836817 -913319025 -8404...

output:

result:

Test #5:

score: 0

Runtime Error

input:

99320 577219
-525813544 -959369807 -718451747 -533082399 -787662356 -531754846 -650759294 -381852570 -979346470 -644489626 -425559804 -332888497 -203462089 -292970440 -958637976 -533593640 53499163 -331134986 -296264838 -806780896 -651958364 -547743072 -590243769 -75974484 -843772303 -367318307 -443...

output:

result:

Test #6:

score: 10

Accepted

time: 55ms

memory: 23508kb

input:

90498 99230
-33558917 30715649 81001133 -12438113 81315374 -70949846 -71212693 66569129 -16194103 -63049353 -79869090 97189792 61301532 53180861 -26423528 -30279746 32502058 7951680 -97121356 -5044511 -4113729 82719257 96311627 80260870 -29075735 -31473462 -27928703 81572824 -89715849 85470402 -5284...

output:

result:

ok 50858 numbers

Test #7:

score: 0

Wrong Answer

time: 48ms

memory: 28252kb

input:

99124 99428
-29121705 73122072 14759978 -93785828 -52964748 50664810 -67789167 38732351 -57330970 48764999 -73647685 92261655 2267455 -21312555 -51092994 33675829 40607569 -85559394 -93024695 24124094 -45466947 -66665193 -99870070 -58435829 -56724651 -98854388 86610996 59912463 -27223092 85984568 94...

output:

result:

wrong answer 1st numbers differ - expected: '106340510', found: '106138754'

Test #8:

score: 0

Wrong Answer

time: 110ms

memory: 93656kb

input:

99538 99031
-501609067 -774687736 -928215759 -477038092 -823455674 -871460165 -852927043 -704708804 -775793387 -521621627 -923721630 -811686668 -952989802 -841891941 -482572032 -509003031 -595485934 -831251065 -616219801 -580804479 -951849211 -783134298 -505096225 -625789647 -520043618 -798430551 -6...

output:

result:

wrong answer 1st numbers differ - expected: '999996555', found: '999977676'

Test #9:

score: 0

Runtime Error

input:

99483 590517
-508842 -191922 830365 -321837 163127 -225035 -3981 -222030 721775 -244372 -342954 -692168 -156349 -853744 -606213 687012 -401837 -920227 -198596 -14000 -345069 -628969 -386394 -590462 97339 -974255 -551821 -623120 -673402 -567398 278012 511781 29418 -975780 -416796 902045 -565858 -2455...

output:

result:

Test #10:

score: 0

Runtime Error

input:

99801 597343
-32417 984702 259080 747296 807167 169192 454040 -426594 582296 321692 800273 962596 -968901 42596 -304443 574664 936854 271860 902411 38804 -688175 55613 31189 -930407 -544084 -164683 -442201 118338 -858190 -109300 682685 896380 -887043 357053 -908865 890420 -680972 632527 -106741 -668...