oj.uz

Submission #1116543

# Submission time Handle Problem Language Result Execution time Memory
1116543 2024-11-21T19:39:58 Z Sofiatpc Xylophone (JOI18_xylophone) C++17
0 / 100
 173 ms 336 KB 
#include <bits/stdc++.h>
#include "xylophone.h"

using namespace std;

int v[5005];

void calc(int l, int r, int p, int m){
	if(r <= l)return;

	int nm;
	if(m == 0)nm = 0;
	else nm = 5005;

	if(p == 0){
		int last = l;
		for(int i = l+1; i <= r; i++){
			int x = query(l,i);
			if(m == 0 && x > nm){//sou min acho max
				v[i] = v[l]+x;
				nm = x;
				calc(last+1,i,1,1);
				last = i;
			}else if(m == 1 && x < nm){//sou max acho min
				v[i] = v[l]-x;
				nm = x;
				calc(last+1,i,1,0);
				last = i;
			}
		}

		if(m == 0)calc(last,r,0,1);
		else calc(last,r,0,0);
	}else{
		int last = r;
		for(int i = r-1; i >= l; i--){
			int x = query(i,r);
			if(m == 0 && x > nm){//sou min acho max
				v[i] = v[r]+x;
				nm = x;
				calc(1,last-1,0,1);
				last = i;
			}else if(m == 1 && x < nm){//sou max acho min
				v[i] = v[r]-x;
				nm = x;
				calc(1,last-1,0,0);
				last = i;
			}
		}
		if(m == 0)calc(l,last,1,1);
		else calc(l,last,1,0);
	}
}

void solve(int n) {
	int l = 1, r = n;
	while(l!= r){
		int mid = (l+r+1)/2;
		if(query(mid,n) == n-1)l = mid;
		else r = mid-1;
	}

	v[l] = 1;
	calc(l,n,0,0);
	calc(1,l,1,0);

	for(int i = 1; i <= n; i++)answer(i,v[i]);
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 36.0

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

Subtask #3
0 / 53.0

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