제출 #845987

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

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
const ll INF=2e18;
struct T{
    ll l,r;
    pii P={INF,INF};
    T *left=nullptr,*right=nullptr;
    T(ll l, ll r){
        this->l=l;
        this->r=r;
    }
    void extend(){
        if (!left&&l<r) {
            ll mid=(l+r)>>1;
            left=new T(l,mid);
            right=new T(mid+1,r);
        }
    }
    void update(ll u, ll v, pii p){
        if (l>v||r<u||l>r||u>v)
            return;
        if (l>=u&&r<=v){
            P=min(P,p);
            return;
        }
        extend();
        left->update(u,v,p);
        right->update(u,v,p);
    }
    pii get(ll i){
        pii p={INF,i};
        auto node=this;
        while (node){
            p=min(p,node->P);
            ll mid=(node->l+node->r)>>1;
            if (mid>=i)
                node=node->left;
            else
                node=node->right;
        }
        return p;
    }
}*root=new T(0,INF);
vector <pair <pii, int>> v;
ll e[1001][1001],r[1001][1001],n,t[1001],w[1001],l,x,id;
void init(int L, int N, vector <ll> T, vector <int> W, int X, int m, vector <int> s){
    l=L;
    x=X;
    for (int i=0;i<N;i++){
        if (W[i]>x){
            w[n]=W[i];
            e[n][0]=t[n]=T[i];
            n++;
        }
    }
    for (int i=1;i<m;i++){
        for (int j=0;j<n;j++)
            v.push_back({{e[j][i-1],w[j]},j});
        sort(v.begin(),v.end());
        ll mx=0;
        for (int it=0;it<v.size();it++){
            int j=v[it].second;
            mx=max(mx,e[j][i-1]+w[j]*(s[i]-s[i-1]));
            e[j][i]=mx;
            r[j][i-1]=min((it==v.size()-1?INF:e[v[it+1].second][i-1]),mx-x*(s[i]-s[i-1]));
        }
        v.clear();
    }
    for (int i=m-1;i;i--){
        for (int j=0;j<n;j++)
            v.push_back({{e[j][i],w[j]},j});
        sort(v.begin(),v.end());
        for (auto p:v){
            int j=p.second;
            root->update(e[j][i-1]+1+x*(l-s[i-1]),r[j][i-1]+x*(l-s[i-1]),{i,root->get(e[j][i]+x*(l-s[i])).second});
        }
        v.clear();
    }
}
ll arrival_time(ll y){
    return root->get(y+x*l).second;
}

컴파일 시 표준 에러 (stderr) 메시지

overtaking.cpp: In function 'void init(int, int, std::vector<long long int>, std::vector<int>, int, int, std::vector<int>)':
overtaking.cpp:64:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for (int it=0;it<v.size();it++){
      |                       ~~^~~~~~~~~
overtaking.cpp:68:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             r[j][i-1]=min((it==v.size()-1?INF:e[v[it+1].second][i-1]),mx-x*(s[i]-s[i-1]));
      |                            ~~^~~~~~~~~~~~

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