oj.uz

답안 #964977

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
964977 2024-04-17T22:54:04 Z MarwenElarbi Bitaro's travel (JOI23_travel) C++17
0 / 100
 15 ms 4392 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define vi vector<int>
#define ve vector
#define ll long long
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define onbit __builtin_popcount
#define ii pair<int,int>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e18
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e5+5
using namespace std;
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll MOD = 1e9+7;
const int nax = 1e5+5;
const int MAX_VAL = 1e6+1;
double PI=3.14159265359;
int arx[8]={1,0,0,-1,-1,-1, 1, 1};
int ary[8]={0,1,-1, 0, 1,-1,-1, 1};
void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
vector<int> tab(nax);
vector<int> nl(nax);
vector<int> nr(nax);
int lg[nax];
int spr[nax][18];
int spl[nax][18];
int ask_left(int l,int r){
    int cur=lg[r-l];
    return min(spl[l][cur],spl[r-(1<<cur)+1][cur]);
}
int ask_right(int l,int r){
    int cur=lg[r-l];
    //cout <<"ask"<<" "<<l<<" "<<r<<" "<<max(spr[l][cur],spr[r-(1<<cur)+1][cur])<<endl;
    //cout <<l<<" "<<r<<" "<<spr[1][cur]<<" "<<cur<<endl;
    return max(spr[l][cur],spr[r-(1<<cur)+1][cur]);
}
int main(){
    optimise;
    //setIO("dec");
    lg[1]=0;
    for (int i = 2; i < nax; ++i)
    {
        lg[i]=lg[i/2]+1;
    }
    int n;
    cin>>n;
    tab.resize(n);
    for (int i = 0; i < n; ++i)
    {
        cin>>tab[i];
    }
    nr[0]=tab[n-1];
    nl[n-1]=tab[0];
    spr[0][0]=nr[0];
    spl[n-1][0]=nl[0];
    for (int i = 0; i < n-1; ++i)
    {
        int cur=tab[i+1]-tab[i];
        int l=-1;
        int r=i;
        while(r-l>1){
            int mid=(r+l)/2;
            if(tab[i]-tab[mid]>=cur) l=mid;
            else r=mid; 
        }
        nl[i]=tab[r];
        spl[i][0]=nl[i];
        //cout <<nl[i]<<" ";
    }//cout <<endl;
    for (int i = n-1; i > 0; --i)
    {
        int cur=tab[i]-tab[i-1];
        int l=i;
        int r=n;
        while(r-l>1){
            int mid=(r+l)/2;
            if(tab[mid]-tab[i]<cur) l=mid;
            else r=mid; 
        }
        nr[i]=tab[l];
        spr[i][0]=nr[i];
        //if(i==132) cout <<nr[i]<<endl;
        //cout <<nr[i]<<" ";
    }//cout <<endl;
    for (int i = 1; i < 18; ++i)
    {
        //cout <<"3asba"<<endl;
        for (int j = 0; j+(1<<i) < n; ++j)
        {
            spl[j][i]=min(spl[j][i-1],spl[j+(1<<(i-1))][i-1]);
        }
        for (int j = 0; j+(1<<i)< n; j++)
        {
            spr[j][i]=max(spr[j][i-1],spr[j+(1<<(i-1))][i-1]);
        }
    }
    //cout <<spl[1000][0]<<" "<<nl[1000]<<endl;
    //cout <<ask_left(1000,1000)<<endl;
    int q;
    cin>>q;
    while(q--){
        //out <<"nea"<<endl;
        int x;
        cin>>x;
        long long ans=0;
        if(x>=tab[n-1]){
            cout <<x-tab[0]<<endl;
            continue;
        }else if(x<=tab[0]){
            cout <<tab[n-1]-x<<endl;
            continue;
        }
        int idx=upper_bound(tab.begin(),tab.end(),x)-tab.begin();
        bool test=false;
        if(tab[idx-1]==x) test=true;
        int cur;
        if(tab[idx]-x<x-tab[idx-1-test]){
            cur=1;
        }else{
            idx--;
            cur=0;
        }
        int lefty=x;
        int righty=x;
        int t=10;
        while(lefty>tab[0]&&righty<tab[n-1]){
            //cout <<"new "<<lefty<<" "<<righty<<" "<<cur<<endl;
            if(cur==1){
                int l=idx;
                int r=n-1;
                while(r-l>1){
                    int mid=(r+l)/2;
                    if(ask_left(idx,mid)>=lefty) l=mid;
                    else r=mid;
                }
                //cout <<idx<<" "<<nl[r]<<" "<<lefty<<" "<<ask_left(idx,r)<<endl;
                ans+=tab[r]-lefty;
                righty=tab[r];
                idx=r;
                cur=0;
            }else{
                int l=0;
                int r=idx;
                while(r-l>1){
                    int mid=(r+l)/2;
                    if(ask_right(mid,idx)<=righty) r=mid;
                    else l=mid;
                    //cout <<ask_right(649,idx)<<" "<<l<<" "<<r<<endl;
                }
                //cout <<spr[idx][0]<<" "<<idx<<" "<<ask_right(l,idx)<<" "<<righty<<endl;
                ans+=righty-tab[l];
                lefty=tab[l];
                idx=l;
                cur=1;
            }
            //cout <<lefty<<" "<<righty<<endl;
            if(!t--) break;
        }
        //cout <<ans<<" "<<lefty<<" "<<righty<<endl;
        if(righty<tab[n-1]) ans+=tab[n-1]-lefty;
        if(lefty>tab[0]) ans+=righty-tab[0];
        cout << ans<<endl;
    }
}

Compilation message

travel.cpp: In function 'void setIO(std::string)':
travel.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
travel.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3928 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4108 KB Output is correct
5 Correct 2 ms 4188 KB Output is correct
6 Correct 2 ms 4340 KB Output is correct
7 Correct 2 ms 4188 KB Output is correct
8 Correct 1 ms 3928 KB Output is correct
9 Correct 1 ms 3932 KB Output is correct
10 Correct 1 ms 3932 KB Output is correct
11 Correct 1 ms 3932 KB Output is correct
12 Correct 1 ms 4184 KB Output is correct
13 Incorrect 1 ms 4096 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3928 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4108 KB Output is correct
5 Correct 2 ms 4188 KB Output is correct
6 Correct 2 ms 4340 KB Output is correct
7 Correct 2 ms 4188 KB Output is correct
8 Correct 1 ms 3928 KB Output is correct
9 Correct 1 ms 3932 KB Output is correct
10 Correct 1 ms 3932 KB Output is correct
11 Correct 1 ms 3932 KB Output is correct
12 Correct 1 ms 4184 KB Output is correct
13 Incorrect 1 ms 4096 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Correct 1 ms 3928 KB Output is correct
3 Correct 2 ms 3932 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 1 ms 3932 KB Output is correct
6 Correct 1 ms 3932 KB Output is correct
7 Runtime error 15 ms 4392 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3928 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4108 KB Output is correct
5 Correct 2 ms 4188 KB Output is correct
6 Correct 2 ms 4340 KB Output is correct
7 Correct 2 ms 4188 KB Output is correct
8 Correct 1 ms 3928 KB Output is correct
9 Correct 1 ms 3932 KB Output is correct
10 Correct 1 ms 3932 KB Output is correct
11 Correct 1 ms 3932 KB Output is correct
12 Correct 1 ms 4184 KB Output is correct
13 Incorrect 1 ms 4096 KB Output isn't correct
14 Halted 0 ms 0 KB -