제출 #842859

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
842859		Huseyn123	추월 (IOI23_overtaking)	C++17	39 / 100	3638 ms	2039428 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
#define MAX 8000001
#define INF LLONG_MAX
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ins insert
#define ff first
#define ss second
#define gett(x,m) get<m>(x)
#define all(a) a.begin(),a.end()
#define lb(a,b) lower_bound(all(a),b)
#define ub(a,b) upper_bound(all(a),b)
#define sortv(a) sort(all(a))
#define sorta(a,sz) sort(a,a+sz)
#define inputar(a,b){\
    for(int i=0;i<b;i++){\
        cin >> a[i];\
    }\
}
#define inputvec(a,b){\
    for(int i=0;i<b;i++){\
        ll num;\
        cin >> num;\
        a.pb(num);\
    }\
}
#define outputar(a,b){\
    for(int i=0;i<b;i++){\
        cout << a[i] << " ";\
    }\
    cout << "\n";\
}
#define outputvec(a){\
    for(auto x:a){\
        cout << x << " ";\
    }\
    cout << "\n";\
}
#define reset(a,n,v){\
    for(int i=0;i<n;i++){\
        a[i]=v;\
    }\
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll,ll> tll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef double db;
typedef long double ldb;
ll n,m,q,spd,road_len,b[1001],d[1001]; 
ll a[1001];
ll e[1001][1001]; 
vector<pll> g[1001];
ll p[1001][1001];
ll v[1001][1001];
pll pmax=mp(INF,INF);
struct node{
    pll res,lazy;
    ll l,r,rn,ln; 
    node(): res(pmax),lazy(pmax),rn(-1),ln(-1){}
};
vector<node> tree(MAX);
ll cnt=0;
pll fmax(pll p1,pll p2){
    if(p1==pmax){
        return p2; 
    }
    if(p2==pmax){
        return p1;
    }
    if(p1.ff<p2.ff){
        return p1;
    }
    else if(p1.ff==p2.ff){
        if(e[p1.ss][p1.ff]>e[p2.ss][p2.ff]){
            return p1;
        }
        else{
            return p2;
        }
    }
    else{
        return p2;
    }
}
void propogate(int x){
    if(tree[x].lazy!=pmax){
        tree[x].res=fmax(tree[x].res,tree[x].lazy);
        if(tree[x].r-tree[x].l==0){
            return;
        }
        ll mid=(tree[x].l+tree[x].r)/2;
        if(tree[x].ln==-1){
            tree[x].ln=cnt;
            tree[cnt].l=tree[x].l;
            tree[cnt].r=mid;
            cnt++;
        }
        if(tree[x].rn==-1){
            tree[x].rn=cnt;
            tree[cnt].l=mid+1;
            tree[cnt].r=tree[x].r;
            cnt++;
        }
        tree[tree[x].ln].lazy=fmax(tree[tree[x].ln].lazy,tree[x].lazy);
        tree[tree[x].rn].lazy=fmax(tree[tree[x].rn].lazy,tree[x].lazy);
        tree[x].lazy=pmax;
    }
}
void upd(int x,ll l,ll r,pll p1){
    propogate(x);
    if(l==tree[x].l && r==tree[x].r){
        tree[x].lazy=p1;
        propogate(x);
        return;
    }
    ll mid=(tree[x].l+tree[x].r)/2;
    if(tree[x].ln==-1){
        tree[x].ln=cnt;
        tree[cnt].l=tree[x].l;
        tree[cnt].r=mid;
        cnt++;
    }
    if(tree[x].rn==-1){
        tree[x].rn=cnt;
        tree[cnt].l=mid+1;
        tree[cnt].r=tree[x].r;
        cnt++;
    }
    if(l>mid){
        upd(tree[x].rn,l,r,p1);
    }
    else if(r<=mid){
        upd(tree[x].ln,l,r,p1);
    }
    else{
        upd(tree[x].ln,l,mid,p1);
        upd(tree[x].rn,mid+1,r,p1);
    }
    propogate(tree[x].ln);
    propogate(tree[x].rn);
    tree[x].res=fmax(tree[tree[x].ln].res,tree[tree[x].rn].res);
}
pll get(int x,ll l,ll r){
    propogate(x);
    if(tree[x].l==l && tree[x].r==r){
        return tree[x].res;
    }
    ll mid=(tree[x].l+tree[x].r)/2;
    if(tree[x].ln==-1){
        tree[x].ln=cnt;
        tree[cnt].l=tree[x].l;
        tree[cnt].r=mid;
        cnt++;
    }
    if(tree[x].rn==-1){
        tree[x].rn=cnt;
        tree[cnt].l=mid+1;
        tree[cnt].r=tree[x].r;
        cnt++;
    }
    if(l>mid){
        return get(tree[x].rn,l,r);
    }
    else if(r<=mid){
        return get(tree[x].ln,l,r);
    }
    else{
        return fmax(get(tree[x].ln,l,mid),get(tree[x].rn,mid+1,r));
    }
}
ll H=1e18;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    tree[cnt].l=0; 
    tree[cnt].r=3e18; 
    cnt++;
	road_len=L; 
	n=N; 
	spd=X;
	m=M;
    for(int i=0;i<n;i++){
        a[i]=T[i];
    }
    // a avtobusların çıxma vaxtı üçün 
    for(int i=0;i<n;i++){
        b[i]=W[i];
    }
    // b avtobusların sürətləri üçün 
    for(int i=0;i<m;i++){
        d[i]=S[i];
    }
    // d stansiyalar üçün
    // e stansiyalara çatma vaxtı üçün 
    // p g prefix max üçün 
    for(int i=0;i<n;i++){
        e[i][0]=a[i]; 
    }
    for(int j=1;j<m;j++){
        vector<pll> f; // avtobusların stansiyaya çatma vaxtına əsasən sıralayıb digər stansiyaya çatma vaxtını o(n)-ə hesablamaq üçün
        for(int i=0;i<n;i++){
            f.pb(mp(e[i][j-1],i));
        }
        sortv(f);
        g[j-1]=f;
        ll h=-1; // digər stansiyaya max çatma vaxtı 
        int z=0; 
        while(z<n){
            int z1=z; 
            while(z1<n && f[z1].ff==f[z].ff){
                e[f[z1].ss][j]=max(h,f[z1].ff+b[f[z1].ss]*(d[j]-d[j-1]));
                z1++;
            }
            while(z<z1){
                h=max(h,e[f[z].ss][j]); 
                z++;
            }
        }
    }
    vector<pll> f; 
    for(int i=0;i<n;i++){
        f.pb(mp(e[i][m-1],i)); 
    }
    sortv(f); 
    g[m-1]=f;
    for(int j=0;j<m;j++){
        p[0][j]=g[j][0].ff;
        for(int i=1;i<n;i++){
            p[i][j]=max(p[i-1][j],g[j][i].ff);
        }
    }
    for(int j=m-1;j>=1;j--){
        for(int i=0;i<n;i++){
            pll p1=get(0,e[i][j]-spd*d[j]+H,e[i][j]-spd*d[j]+H);
            if(p1==pmax){
                v[i][j]=e[i][j]+(d[m-1]-d[j])*spd; 
            }
            else{
                v[i][j]=v[p1.ss][p1.ff];
            }
        }
        for(int i=0;i<n;i++){
            pll p1=mp((ll)j,(ll)i);
            if(e[i][j]-spd*d[j]+H>=e[i][j-1]-spd*d[j-1]+H+1){
                upd(0,e[i][j-1]-spd*d[j-1]+H+1,e[i][j]-spd*d[j]+H,p1);
            }
        }
    }
    tree.clear(); 
    tree.resize(MAX);
    for(int j=m-1;j>=1;j--){
        for(int i=0;i<n;i++){
            pll p1=mp((ll)j,(ll)i);
            if(e[i][j]-spd*d[j]+H>=e[i][j-1]-spd*d[j-1]+H+1){
                upd(0,e[i][j-1]-spd*d[j-1]+H+1,e[i][j]-spd*d[j]+H,p1);
            }
        }
    }
    return;
}

long long arrival_time(long long Y)
{
	ll x=Y;
	pll p1=get(0,x+H,x+H);
    if(p1==pmax){
        return x+spd*d[m-1];
    }
    else{
        return v[p1.ss][p1.ff];
    }
}

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 0 / 26
• Subtask 5: 0 / 35