oj.uz

답안 #828930

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
828930 2023-08-17T20:50:48 Z arnold518 송신탑 (IOI22_towers) C++17
0 / 100
 4000 ms 7380 KB 
#include "towers.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int INF = 1e9+7;

int N, A[MAXN+10];

struct SEG
{
	pii minv[MAXN*4+10], maxv[MAXN*4+10];
	void init(int node, int tl, int tr)
	{
		if(tl==tr)
		{
			minv[node]={A[tl], tl};
			maxv[node]={A[tl], tl};
			return;
		}
		int mid=tl+tr>>1;
		init(node*2, tl, mid);
		init(node*2+1, mid+1, tr);
		minv[node]=min(minv[node*2], minv[node*2+1]);
		maxv[node]=max(maxv[node*2], maxv[node*2+1]);
	}
	pii query1(int node, int tl, int tr, int l, int r)
	{
		if(l<=tl && tr<=r) return minv[node];
		if(r<tl || tr<l) return {INF, 0};
		int mid=tl+tr>>1;
		return min(query1(node*2, tl, mid, l, r), query1(node*2+1, mid+1, tr, l, r));
	}
	pii query2(int node, int tl, int tr, int l, int r)
	{
		if(l<=tl && tr<=r) return maxv[node];
		if(r<tl || tr<l) return {-INF, 0};
		int mid=tl+tr>>1;
		return max(query2(node*2, tl, mid, l, r), query2(node*2+1, mid+1, tr, l, r));
	}
}seg;

void init(int _N, vector<int> _H)
{
	N=_N;
	for(int i=1; i<=N; i++) A[i]=_H[i-1];
	seg.init(1, 1, N);
}

int solve(int l, int r, int d)
{
	//printf("%d %d %d\n", l, r, d);
	if(l>r) return 0;
	int ret=0;
	pii p=seg.query2(1, 1, N, l, r);
	int lv=solve(l, p.second-1, d), rv=solve(p.second+1, r, d);
	int mv=seg.query1(1, 1, N, l, p.second-1).first;
	if(mv>p.first-d) ret=rv;
	else ret=lv+rv;
	ret=max(ret, 1);
	return ret;
}

int max_towers(int L, int R, int D) 
{
	L++; R++;
	return solve(L, R, D);
}

Compilation message

towers.cpp: In member function 'void SEG::init(int, int, int)':
towers.cpp:25:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |   int mid=tl+tr>>1;
      |           ~~^~~
towers.cpp: In member function 'pii SEG::query1(int, int, int, int, int)':
towers.cpp:35:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |   int mid=tl+tr>>1;
      |           ~~^~~
towers.cpp: In member function 'pii SEG::query2(int, int, int, int, int)':
towers.cpp:42:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |   int mid=tl+tr>>1;
      |           ~~^~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4082 ms 7380 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 336 KB 1st lines differ - on the 1st token, expected: '13', found: '15'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 336 KB 1st lines differ - on the 1st token, expected: '13', found: '15'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4008 ms 5584 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4019 ms 1616 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 336 KB 1st lines differ - on the 1st token, expected: '13', found: '15'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4082 ms 7380 KB Time limit exceeded
2 Halted 0 ms 0 KB -