oj.uz

Submission #991296

# Submission time Handle Problem Language Result Execution time Memory
991296 2024-06-01T18:43:45 Z amirhoseinfar1385 Train (APIO24_train) C++17
100 / 100
 682 ms 311672 KB 
//khodaya komak kon
#include "train.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,maxw=maxn*4;
vector<int>allind;
long long n,m,w,allt[maxn];
long long inf=1e17;
int dproot[maxw];

int kaf=(1<<19),root=0;
struct segment{
    struct node{
        int rc,lc,w;
        node(){
            rc=lc=w=0;
        }
    };
    int ts=(1<<20);
    node seg[(1<<20)*20];
    segment(){
        for(int i=1;i<kaf;i++){
            seg[i].rc=((i<<1)^1);
            seg[i].lc=(i<<1);
        }
    }
    int upd(int i,int l,int r,int tl,int tr,int w){
        if(l>r||l>tr||r<tl||tl>tr){
            return i;
        }
        if(l>=tl&&r<=tr){
            seg[ts]=seg[i];
            seg[ts].w+=w;
            ts++;
            return ts-1;
        }
        int m=(l+r)>>1;
        int fts=ts;
        ts++;
        seg[fts]=seg[i];
        seg[fts].lc=upd(seg[fts].lc,l,m,tl,tr,w);
        seg[fts].rc=upd(seg[fts].rc,m+1,r,tl,tr,w);
        return fts;
    }
    int pors(int i,int l,int r,int tl,int tr){
        int ret=0;
        while(true){
            ret+=seg[i].w;
            if(l>=tl&&r<=tr){
                return ret;
            }
            int m=(l+r)>>1;
            if(tl<=m){
                i=seg[i].lc;
                r=m;
            }else{
                i=seg[i].rc;
                l=m+1;
            }
           // return pors(seg[i].rc,m+1,r,tl,tr)+pors(seg[i].lc,l,m,tl,tr)+seg[i].w;
        }
    }
}seg;

struct func{
    long long x0,w,ind;
    func(){
        x0=0;
        ind=0;
        w=inf;
    }
    long long get(long long inda){
        inda=min(inda,(long long)allind.size()-1);
        if(inda<x0){
            return w;
        }
        //cout<<"wtf: "<<allind[x0]<<" "<<allind[inda]<<" "<<seg.pors(dproot[x0+1],0,kaf-1,inda,inda)<<endl;
        return w+allt[ind]*seg.pors(dproot[x0+1],0,kaf-1,inda,inda);
    }
    bool operator ==(func f){
        return (f.x0==x0&&f.w==w);
    }
}fakefunc;
 
struct lichao{
    struct node{
        int l,r;
        node(){
            l=r=-1;
        }
        func f;
    };
    vector<node> segl;
    void create(int sz){
        sz+=2;
        segl.resize(sz);
    }
    int te=1;
    int gor(int i){
        if(segl[i].r==-1){
            segl[i].r=te;
            te++;
        }
        return segl[i].r;
    }
    int gol(int i){
        if(segl[i].l==-1){
            segl[i].l=te;
            te++;
        }
        return segl[i].l;
    }
    void add(func f,int i=0,int l=0,int r=1e6){
        if(l==r){
            return ;
        }
        if(segl[i].f==fakefunc){
            segl[i].f=f;
            return ;
        }
        int m=(l+r)/2;
        if(segl[i].f.get(l)>f.get(l)){
            swap(segl[i].f,f);
        }
        if(l==r-1){
            return ;
        }
        if(segl[i].f.get(m)<=f.get(m)){
            add(f,gor(i),m,r);
        }else{
            swap(segl[i].f,f);
            add(f,gol(i),l,m);
        }
    }
    long long pors(int w,int i=0,int l=0,int r=1e6){
        if(l==r){
            return 0;
        }
        long long ret=segl[i].f.get(w);
        long long m=(l+r)>>1;
        if(w>=m&&segl[i].r!=-1){
            ret=min(ret,pors(w,segl[i].r,m,r));
        }
        if(w<m&&segl[i].l!=-1){
            ret=min(ret,pors(w,segl[i].l,l,m));
        }
        return ret;
    }
}lich[maxn];

struct yal{
    int u,v,l,r,w;
}alle[maxn];
vector<int>adj[maxw];
int cnt[maxn];
vector<pair<int,int>>allw;
vector<int>allwi[maxw];
vector<func>addy[maxw];
void preq(){
    for(auto x:allw){
        allwi[x.first].push_back(x.second);
    }
    for(long long i=maxw-1;i>=0;i--){
        for(auto x:allwi[i]){
            root=seg.upd(root,0,kaf-1,x,(int)allind.size(),1);
        }
        dproot[i]=root;
    }
}

long long solve(int N, int M, int W, vector<int> T, vector<int> X, vector<int> Y,
                vector<int> A, vector<int> B, vector<int> C, vector<int> L,
                vector<int> R) {
	n=N;
    m=M;
    w=W;
    for(int i=0;i<n;i++){
        allt[i]=T[i];
    }
    allind.push_back(0);
    for(int i=0;i<m;i++){
        allind.push_back(A[i]);
        allind.push_back(B[i]);
    }
    for(int i=0;i<w;i++){
        allind.push_back(L[i]);
        allind.push_back(R[i]);
    }
    sort(allind.begin(),allind.end());
    allind.resize(unique(allind.begin(),allind.end())-allind.begin());
    for(int i=0;i<m;i++){
        A[i]=lower_bound(allind.begin(),allind.end(),A[i])-allind.begin();
        B[i]=lower_bound(allind.begin(),allind.end(),B[i])-allind.begin();
    }
    for(int i=0;i<w;i++){
        L[i]=lower_bound(allind.begin(),allind.end(),L[i])-allind.begin();
        R[i]=lower_bound(allind.begin(),allind.end(),R[i])-allind.begin();
        allw.push_back(make_pair(L[i],R[i]));
    }
    preq();
    for(int i=0;i<m;i++){
        alle[i].u=X[i];
        alle[i].v=Y[i];
        alle[i].w=C[i];
        alle[i].l=A[i];
        alle[i].r=B[i];
        cnt[alle[i].v]++;
    //    //cout<<"wtf "<<alle[i].l<<endl;
        adj[alle[i].l].push_back(i);
    //    //cout<<"nago"<<endl;
    }
    for(int i=0;i<n;i++){
    //    //cout<<"injy"<<endl;
        lich[i].create(cnt[i]);
    //    //cout<<"oonjy"<<endl;
        func f;
        if(i==0){
            f.w=0;
        }else{
            f.w=inf;
        }
    //    //cout<<"salam"<<endl;
        f.x0=0;
        f.ind=i;
        lich[i].add(f);
    //    //cout<<"by"<<endl;
    }
    ////cout<<"salam"<<endl;
    for(int i=0;i<maxw;i++){
        for(auto x:addy[i]){
            lich[x.ind].add(x);
        }
        for(auto x:adj[i]){
            long long w=lich[alle[x].u].pors(alle[x].l-1);
            w+=alle[x].w;
            //cout<<"pors: "<<alle[x].u<<" "<<alle[x].v<<" "<<allind[alle[x].l]<<" "<<allind[alle[x].r]<<" "<<alle[x].w<<" "<<w<<endl;
            func f;
            f.ind=alle[x].v;
            f.w=w;
            f.x0=alle[x].r;
            addy[alle[x].r].push_back(f);
        }
    }
    if(lich[n-1].pors(maxw+1)>=inf){
        return -1;
    }
    return lich[n-1].pors(maxw+1);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 279584 KB Correct.
2 Correct 113 ms 279632 KB Correct.
3 Correct 106 ms 279600 KB Correct.
4 Correct 109 ms 279636 KB Correct.
5 Correct 104 ms 279380 KB Correct.
6 Correct 107 ms 279380 KB Correct.
7 Correct 104 ms 279380 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 296392 KB Correct.
2 Correct 245 ms 305220 KB Correct.
3 Correct 104 ms 279324 KB Correct.
4 Correct 119 ms 288848 KB Correct.
5 Correct 105 ms 279380 KB Correct.
6 Correct 499 ms 295616 KB Correct.
7 Correct 104 ms 279512 KB Correct.
8 Correct 457 ms 304836 KB Correct.
9 Correct 236 ms 305352 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 296392 KB Correct.
2 Correct 245 ms 305220 KB Correct.
3 Correct 104 ms 279324 KB Correct.
4 Correct 119 ms 288848 KB Correct.
5 Correct 105 ms 279380 KB Correct.
6 Correct 499 ms 295616 KB Correct.
7 Correct 104 ms 279512 KB Correct.
8 Correct 457 ms 304836 KB Correct.
9 Correct 236 ms 305352 KB Correct.
10 Correct 391 ms 302788 KB Correct.
11 Correct 334 ms 311460 KB Correct.
12 Correct 118 ms 288852 KB Correct.
13 Correct 113 ms 279380 KB Correct.
14 Correct 628 ms 301772 KB Correct.
15 Correct 347 ms 311492 KB Correct.
16 Correct 632 ms 301848 KB Correct.
17 Correct 444 ms 311176 KB Correct.

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 279584 KB Correct.
2 Correct 113 ms 279632 KB Correct.
3 Correct 106 ms 279600 KB Correct.
4 Correct 109 ms 279636 KB Correct.
5 Correct 104 ms 279380 KB Correct.
6 Correct 107 ms 279380 KB Correct.
7 Correct 104 ms 279380 KB Correct.
8 Correct 280 ms 296392 KB Correct.
9 Correct 245 ms 305220 KB Correct.
10 Correct 104 ms 279324 KB Correct.
11 Correct 119 ms 288848 KB Correct.
12 Correct 105 ms 279380 KB Correct.
13 Correct 499 ms 295616 KB Correct.
14 Correct 104 ms 279512 KB Correct.
15 Correct 457 ms 304836 KB Correct.
16 Correct 236 ms 305352 KB Correct.
17 Correct 391 ms 302788 KB Correct.
18 Correct 334 ms 311460 KB Correct.
19 Correct 118 ms 288852 KB Correct.
20 Correct 113 ms 279380 KB Correct.
21 Correct 628 ms 301772 KB Correct.
22 Correct 347 ms 311492 KB Correct.
23 Correct 632 ms 301848 KB Correct.
24 Correct 444 ms 311176 KB Correct.
25 Correct 362 ms 311672 KB Correct.
26 Correct 362 ms 311488 KB Correct.
27 Correct 393 ms 311492 KB Correct.
28 Correct 380 ms 311488 KB Correct.
29 Correct 433 ms 302684 KB Correct.
30 Correct 601 ms 301744 KB Correct.
31 Correct 636 ms 301872 KB Correct.
32 Correct 655 ms 301960 KB Correct.
33 Correct 669 ms 301760 KB Correct.
34 Correct 594 ms 301764 KB Correct.
35 Correct 569 ms 301764 KB Correct.
36 Correct 625 ms 301760 KB Correct.
37 Correct 344 ms 311460 KB Correct.
38 Correct 682 ms 301716 KB Correct.
39 Correct 617 ms 301760 KB Correct.
40 Correct 364 ms 311620 KB Correct.
41 Correct 351 ms 307400 KB Correct.
42 Correct 385 ms 298876 KB Correct.
43 Correct 578 ms 297924 KB Correct.
44 Correct 386 ms 311492 KB Correct.
45 Correct 374 ms 311604 KB Correct.
46 Correct 410 ms 311488 KB Correct.
47 Correct 507 ms 311236 KB Correct.
48 Correct 496 ms 309712 KB Correct.
49 Correct 522 ms 309908 KB Correct.
50 Correct 535 ms 309444 KB Correct.
51 Correct 527 ms 309248 KB Correct.
52 Correct 549 ms 309364 KB Correct.