Submission #239480

#	Time	Username	Problem	Language	Result	Execution time	Memory
239480		Dremix10	Xylophone (JOI18_xylophone)	C++17	0 / 100	7 ms	384 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define F first
#define S second
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define maxp 22
#define EPS (ld)(1e-18)
#define mod (int)(1e9+7)
//#define N (int)(1e5+1)


/// ask maxi-mini val from l -> r then x=query(l,r);
/// answer val a for pos i -> answer(i,a);
int arr[5001];
int n;
void left_up(int l, int r);
void left_down(int l, int r);
void right_up(int l, int r);
void right_down(int l, int r);

void left_up(int l, int r){
    int i;
    int maxi=arr[l];
    int idx=-1;
    for(i=l+1;i<=r;i++){
        if(arr[i]!=0){
            maxi=max(maxi,arr[i]);
            continue;
        }
        int x=query(l,i);
        if(x>maxi-arr[l]){
            arr[i]=x+arr[l];
            maxi=arr[i];
            idx=i;
            right_down(l,i);
            //left_down(i,n);
            //left_up(i,n);
        }
    }
    if(idx!=-1)
        left_down(idx,n);
}
void left_down(int l, int r){
    int i;
    int mini=arr[l];
    int idx=-1;
    for(i=l+1;i<=r;i++){
        if(arr[i]!=0){
            mini=min(mini,arr[i]);
            continue;
        }
        int x=query(l,i);
        if(x>arr[l]-mini){
            arr[i]=arr[l]-x;
            mini=arr[i];
            idx=i;
            right_up(l,i);
            //left_down(i,n);
            //left_up(i,n);
        }
    }
    if(idx!=-1)
        left_up(idx,n);
}
void right_up(int l, int r){
    int i;
    int maxi=arr[r];
    int idx=-1;
    for(i=r-1;i>=l;i--){
        if(arr[i]!=0){
            maxi=max(arr[i],maxi);
            continue;
        }
        int x=query(i,r);
        if(x>maxi-arr[r]){
            arr[i]=x+arr[r];
            maxi=arr[i];
            idx=i;
            left_down(i,r);
            //right_down(1,i);
            //right_up(1,i);
        }
    }
    if(idx!=-1)
        right_down(1,idx);

}
void right_down(int l, int r){
    int i;
    int mini=arr[r];
    int idx=-1;
    for(i=r-1;i>=l;i--){
        if(arr[i]!=0){
            mini=min(mini,arr[i]);
            continue;
        }
        int x=query(i,r);
        if(x>arr[r]-mini){
            arr[i]=arr[r]-x;
            mini=arr[i];
            idx=i;
            left_up(i,r);
            //right_down(1,i);
            //right_up(1,i);
        }
    }
    if(idx!=-1)
        right_up(1,idx);
}

void solve(int N) {
    int found;
    int l=1,r=N;
    while(query(l,r)==N-1)
        r--;
    found=r+1;

    int i,j;
    n=N;

    arr[found]=N;
    //cout<<found<<endl;
    right_down(1,found);
    left_down(found,N);

    for(i=1;i<=N;i++){
        //cout<<arr[i]<<" ";
        answer(i,arr[i]);

    }

}

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:123:11: warning: unused variable 'j' [-Wunused-variable]
     int i,j;
           ^

• Subtask 1: 0 / 11
• Subtask 2: 0 / 36
• Subtask 3: 0 / 53