oj.uz

Submission #965451

# Submission time Handle Problem Language Result Execution time Memory
965451 2024-04-18T15:45:50 Z red24 Pilot (NOI19_pilot) C++14
26 / 100
 56 ms 37796 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define vi vector<int>
#define pi pair<int, int>
#define vpi vector<pi>
#define vvi vector<vi>
#define mp make_pair
#define pb push_back
#define all(x) x.begin()+1, x.end()
const int INF = (int)1e17;

vi parent, siz;

void create(int x)
{
	parent[x] = x;
	siz[x] = 1;
}

int find(int x)
{
	if (parent[x] == x) return x;
	return parent[x] = find(parent[x]);
}

void unite(int x, int y)
{
	x = find(x);
	y = find(y);

	if (siz[x] < siz[y]) swap(x, y);

	parent[y] = x;
	siz[x] += siz[y];
}

int f(pi x)
{
	return ((x.second-x.first+1)*(x.second-x.first+2))/2;
}

void solve()
{
	int n, q; cin >> n >> q;
	vi a(n+1);
	for (int i = 1; i <= n; i++) cin >> a[i];

	const int mx = (int)1e6+100;
	vi ans(mx+1);
	vvi idx(mx+1);

	for (int i = 1; i <= n; i++)
	{
		idx[a[i]].pb(i);
	}

	int res = 0;

	set<pi> st;
	for (int el = 1; el <= mx; el++)
	{
		for (auto i : idx[el])
		{
			// find next interval
			auto nxt_it = st.upper_bound(mp(i, 0));
			if (nxt_it != st.end())
			{
				if (nxt_it == st.begin())
				{
					if ((*nxt_it).first == i+1)
					{
						pi nxt_replace = mp(i,(*nxt_it).second);
						res -= f(*nxt_it);
						res += f(nxt_replace);
						st.erase(nxt_it);
						st.insert(nxt_replace);
					}
					else
					{
						st.insert(mp(i, i));
						res += 1;
					}
				}
				else
				{
					auto prev_it = prev(nxt_it);
					if ((*nxt_it).first == i+1 && (*prev_it).second == i-1)
					{
						pi nxt_replace = mp((*prev_it).first, (*nxt_it).second);
						res -= f(*nxt_it);
						res -= f(*prev_it);
						res += f(nxt_replace);
						st.erase(nxt_it);
						st.erase(prev_it);
						st.insert(nxt_replace);
					}
					else if ((*nxt_it).first == i+1)
					{
						pi nxt_replace = mp(i, (*nxt_it).second);
						res -= f(*nxt_it);
						res += f(nxt_replace);
						st.erase(nxt_it);
						st.insert(nxt_replace);
					}
					else if ((*prev_it).first == i-1)
					{
						pi nxt_replace = mp((*prev_it).first, i);
						res -= f(*nxt_it);
						res += f(nxt_replace);
						st.erase(prev_it);
						st.insert(nxt_replace);
					}
					else
					{
						st.insert(mp(i,i));
						res++;
					}
				}
			}
			else
			{
				if (st.size() == 0)
				{
					st.insert(mp(i,i));
					res++;
					continue;
				}
				auto prev_it = prev(nxt_it);
				if ((*prev_it).second == i-1)
				{
					pi prev_replace = mp((*prev_it).first, i);
					res -= f(*prev_it);
					res += f(prev_replace);
					st.erase(prev_it);
					st.insert(prev_replace);
				}
				else
				{
					st.insert(mp(i,i));
					res++;
				}
			}
		}
		ans[el] = res;
	}
	while (q--)
	{
		int x; cin >> x;
		cout << ans[x] << '\n';
	}
}
 
int32_t main()
{
	auto begin = std::chrono::high_resolution_clock::now();
	// FASTIO
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
 
 
 
	int T = 1;
	//cin >> T;
	for (int i = 1; i <= T; i++)
	{
		//cout << "Case #" << i << ": ";
		solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31576 KB Output is correct
2 Correct 12 ms 31580 KB Output is correct
3 Correct 11 ms 31580 KB Output is correct
4 Correct 10 ms 31784 KB Output is correct
5 Correct 12 ms 31756 KB Output is correct
6 Correct 11 ms 31576 KB Output is correct
7 Correct 11 ms 31684 KB Output is correct
8 Correct 11 ms 31580 KB Output is correct
9 Correct 11 ms 31580 KB Output is correct
10 Correct 11 ms 31580 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31576 KB Output is correct
2 Correct 12 ms 31580 KB Output is correct
3 Correct 11 ms 31580 KB Output is correct
4 Correct 10 ms 31784 KB Output is correct
5 Correct 12 ms 31756 KB Output is correct
6 Correct 11 ms 31576 KB Output is correct
7 Correct 11 ms 31684 KB Output is correct
8 Correct 11 ms 31580 KB Output is correct
9 Correct 11 ms 31580 KB Output is correct
10 Correct 11 ms 31580 KB Output is correct
11 Incorrect 11 ms 31576 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31576 KB Output is correct
2 Correct 12 ms 31580 KB Output is correct
3 Correct 11 ms 31580 KB Output is correct
4 Correct 10 ms 31784 KB Output is correct
5 Correct 12 ms 31756 KB Output is correct
6 Correct 11 ms 31576 KB Output is correct
7 Correct 11 ms 31684 KB Output is correct
8 Correct 11 ms 31580 KB Output is correct
9 Correct 11 ms 31580 KB Output is correct
10 Correct 11 ms 31580 KB Output is correct
11 Incorrect 11 ms 31576 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31576 KB Output is correct
2 Correct 12 ms 31580 KB Output is correct
3 Correct 11 ms 31580 KB Output is correct
4 Correct 10 ms 31784 KB Output is correct
5 Correct 12 ms 31756 KB Output is correct
6 Correct 11 ms 31576 KB Output is correct
7 Correct 11 ms 31684 KB Output is correct
8 Correct 11 ms 31580 KB Output is correct
9 Correct 11 ms 31580 KB Output is correct
10 Correct 11 ms 31580 KB Output is correct
11 Incorrect 11 ms 31576 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 36700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 37452 KB Output is correct
2 Correct 40 ms 37468 KB Output is correct
3 Correct 38 ms 37460 KB Output is correct
4 Correct 43 ms 37796 KB Output is correct
5 Correct 39 ms 37200 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 37700 KB Output is correct
2 Correct 45 ms 37456 KB Output is correct
3 Correct 44 ms 37320 KB Output is correct
4 Correct 45 ms 37724 KB Output is correct
5 Correct 46 ms 37664 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31576 KB Output is correct
2 Correct 12 ms 31580 KB Output is correct
3 Correct 11 ms 31580 KB Output is correct
4 Correct 10 ms 31784 KB Output is correct
5 Correct 12 ms 31756 KB Output is correct
6 Correct 11 ms 31576 KB Output is correct
7 Correct 11 ms 31684 KB Output is correct
8 Correct 11 ms 31580 KB Output is correct
9 Correct 11 ms 31580 KB Output is correct
10 Correct 11 ms 31580 KB Output is correct
11 Incorrect 56 ms 36700 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31576 KB Output is correct
2 Correct 12 ms 31580 KB Output is correct
3 Correct 11 ms 31580 KB Output is correct
4 Correct 10 ms 31784 KB Output is correct
5 Correct 12 ms 31756 KB Output is correct
6 Correct 11 ms 31576 KB Output is correct
7 Correct 11 ms 31684 KB Output is correct
8 Correct 11 ms 31580 KB Output is correct
9 Correct 11 ms 31580 KB Output is correct
10 Correct 11 ms 31580 KB Output is correct
11 Incorrect 11 ms 31576 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31576 KB Output is correct
2 Correct 12 ms 31580 KB Output is correct
3 Correct 11 ms 31580 KB Output is correct
4 Correct 10 ms 31784 KB Output is correct
5 Correct 12 ms 31756 KB Output is correct
6 Correct 11 ms 31576 KB Output is correct
7 Correct 11 ms 31684 KB Output is correct
8 Correct 11 ms 31580 KB Output is correct
9 Correct 11 ms 31580 KB Output is correct
10 Correct 11 ms 31580 KB Output is correct
11 Incorrect 11 ms 31576 KB Output isn't correct
12 Halted 0 ms 0 KB -