oj.uz

Submission #239480

# Submission time Handle Problem Language Result Execution time Memory
239480 2020-06-15T20:52:56 Z Dremix10 Xylophone (JOI18_xylophone) C++17
0 / 100
 7 ms 384 KB 
#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

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Incorrect 7 ms 384 KB Wrong Answer [4]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Incorrect 7 ms 384 KB Wrong Answer [4]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Incorrect 7 ms 384 KB Wrong Answer [4]
4 Halted 0 ms 0 KB -