답안 #987162

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
987162	2024-05-22T06:57:32 Z	Pyqe	송신탑 (IOI22_towers)	C++17	17 / 100	778 ms	13824 KB

towers

#include <bits/stdc++.h>
#include "towers.h"

using namespace std;

#define mp make_pair
#define fr first
#define sc second

const long long inf=1e18;
long long n,udn=0,a[100069],uds[100069],sq[100069];
multiset<long long> ms;
multiset<pair<long long,pair<long long,long long>>> rg;

void init(int on,vector<int> aa)
{
	long long i,k,l=-1,w,c=0,k2,l2;
	
	n=on;
	for(i=1;i<=n;i++)
	{
		a[i]=aa[i-1];
	}
	ms.insert(-inf);
	ms.insert(inf);
	for(i=1;i<=n;i++)
	{
		if(((i==1||a[i]<a[i-1])&&(i==n||a[i]<a[i+1]))||(i>1&&i<n&&a[i]>max(a[i-1],a[i+1])))
		{
			ms.insert(i);
			if(l!=-1)
			{
				rg.insert({abs(a[l]-a[i]),{l,i}});
			}
			l=i;
			c++;
		}
	}
	c=(c+1)/2;
	sq[0]=c;
	for(;!rg.empty();)
	{
		w=rg.begin()->fr;
		k=rg.begin()->sc.fr;
		l=rg.begin()->sc.sc;
		rg.erase(rg.begin());
		if(ms.find(k)==ms.end()||ms.find(l)==ms.end())
		{
			continue;
		}
		c--;
		udn++;
		uds[udn]=w;
		sq[udn]=c;
		ms.erase(k);
		ms.erase(l);
		k2=*prev(ms.lower_bound(k));
		l2=*ms.upper_bound(l);
		if(k2!=-inf&&l2!=inf)
		{
			rg.insert({abs(a[k2]-a[l2]),{k2,l2}});
		}
	}
}

int max_towers(int lb,int rb,int cw)
{
	long long p=lower_bound(uds+1,uds+udn+1,cw)-uds-1;
	
	return sq[p];
}

Subtask #1

0 / 4.0

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

Subtask #2

0 / 11.0

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

Subtask #3

0 / 12.0

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

Subtask #4

0 / 14.0

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

Subtask #5

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	177 ms	2900 KB	Output is correct
2	Correct	672 ms	9768 KB	Output is correct
3	Correct	654 ms	9780 KB	Output is correct
4	Correct	716 ms	13636 KB	Output is correct
5	Correct	730 ms	13824 KB	Output is correct
6	Correct	686 ms	13512 KB	Output is correct
7	Correct	778 ms	13736 KB	Output is correct
8	Correct	497 ms	1868 KB	Output is correct
9	Correct	546 ms	1868 KB	Output is correct
10	Correct	516 ms	1868 KB	Output is correct
11	Correct	565 ms	1872 KB	Output is correct
12	Correct	96 ms	9780 KB	Output is correct
13	Correct	173 ms	13628 KB	Output is correct
14	Correct	187 ms	13572 KB	Output is correct
15	Correct	10 ms	1864 KB	Output is correct
16	Correct	10 ms	1868 KB	Output is correct
17	Correct	87 ms	9496 KB	Output is correct
18	Correct	112 ms	10040 KB	Output is correct
19	Correct	88 ms	9784 KB	Output is correct
20	Correct	140 ms	13628 KB	Output is correct
21	Correct	170 ms	13624 KB	Output is correct
22	Correct	146 ms	13564 KB	Output is correct
23	Correct	140 ms	13620 KB	Output is correct
24	Correct	10 ms	1868 KB	Output is correct
25	Correct	10 ms	1868 KB	Output is correct
26	Correct	12 ms	1880 KB	Output is correct
27	Correct	9 ms	1872 KB	Output is correct
28	Correct	2 ms	600 KB	Output is correct
29	Correct	3 ms	600 KB	Output is correct
30	Correct	2 ms	600 KB	Output is correct
31	Correct	1 ms	344 KB	Output is correct
32	Correct	1 ms	344 KB	Output is correct
33	Correct	1 ms	344 KB	Output is correct
34	Correct	2 ms	596 KB	Output is correct
35	Correct	2 ms	556 KB	Output is correct
36	Correct	2 ms	600 KB	Output is correct
37	Correct	2 ms	600 KB	Output is correct
38	Correct	2 ms	600 KB	Output is correct
39	Correct	2 ms	600 KB	Output is correct
40	Correct	1 ms	344 KB	Output is correct
41	Correct	1 ms	344 KB	Output is correct
42	Correct	1 ms	344 KB	Output is correct
43	Correct	1 ms	344 KB	Output is correct

Subtask #6

0 / 19.0

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

Subtask #7

0 / 23.0

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