oj.uz

Submission #872338

# Submission time Handle Problem Language Result Execution time Memory
872338 2023-11-12T22:25:41 Z Cyber_Wolf Izbori (COCI22_izbori) C++17
110 / 110
 395 ms 44164 KB 
// Problem: #3 - Izbori
// Contest: DMOJ - COCI '21 Contest 4
// URL: https://dmoj.ca/problem/coci21c4p3
// Memory Limit: 512 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")

using namespace std;
using namespace __gnu_pbds;

#define lg long long
#define ordered_set	tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mid (lr+hr)/2

const lg N = 2e5+5;

lg id;
map<lg, lg> ids;

vector<lg> o[N];

lg n, a[N], fr[2*N+2], seg[(2*N+2) << 2][4];
//sum, arithmetic decreasing, lazy, assign

void doLazy(lg node, lg lr, lg hr)
{
	if(seg[node][3])
	{
		seg[node][0] = seg[node][1] = 0;
		if(lr != hr)
		{
			for(int ch = node*2; ch <= node*2+1; ch++)
			{
				seg[ch][3] |= seg[node][3];
				seg[ch][2] = 0;
			}
		}
		seg[node][3] = 0;
	}
	if(seg[node][2])
	{
		seg[node][0] += seg[node][2]*(hr-lr+1);
		lg x = (hr-lr+1)*(hr-lr+2)/2;
		seg[node][1] += x*seg[node][2];
		if(lr != hr)
		{
			for(int ch = node*2; ch <= node*2+1; ch++)
			{
				seg[ch][2] += seg[node][2];
			}
		}
		seg[node][2] = 0;
	}
	return;
}

void update(lg node, lg lr, lg hr, lg lq, lg hq, lg val)
{
	if(lq > hq)	return;
	doLazy(node, lr, hr);
	if(lr > hq || lq > hr)	return;
	if(lq <= lr && hr <= hq)	
	{
		seg[node][2] += val;
		doLazy(node, lr, hr);
		return ;
	}
	update(node << 1, lr, mid, lq, hq, val);
	update(node << 1 | 1, mid+1, hr, lq, hq, val);
	seg[node][0] = seg[node << 1][0]+seg[node << 1 | 1][0];
	seg[node][1] = seg[node << 1][1]+seg[node << 1][0]*(hr-mid)+seg[node << 1 | 1][1];
	return;
}

lg get(lg node, lg lr, lg hr, lg lq, lg hq, lg t)
{
	if(lq > hq)	return 0;
	doLazy(node, lr, hr);
	if(lq > hr || lr > hq)	return 0;
	if(lq <= lr && hr <= hq)
	{
		if(t)	
		{
			return seg[node][0]*(hq-hr)+seg[node][1];
		}
		return seg[node][0];
	}
	lg l = get(node << 1, lr, mid, lq, hq, t);
	lg r = get(node << 1 | 1, mid+1, hr, lq, hq, t);
	return l+r;
}

int main()
{
	fastio;
	cin >> n;
	for(int i = 1; i <= n; i++)	o[i].push_back(0);
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
		if(!ids.count(a[i]))
		{
			ids[a[i]] = ++id;
		}
		a[i] = ids[a[i]];
		o[a[i]].push_back(i);
	}
	for(int i = 1; i <= n; i++)	o[i].push_back(n+1);
	lg ans = 0;
	for(int i = 1; i <= n; i++)
	{
		if(o[i].size() <= 2)	continue;
		lg lstVal = 0;
		update(1, 1, 2*n+1, n+2-o[i][1], n+1, 1);
		for(int j = 1; j+1 < o[i].size(); j++)
		{
			lstVal -= (o[i][j]-o[i][j-1]-1);
			lstVal++;
			lg st = lstVal-(o[i][j+1]-o[i][j])+1;
			ans += get(1, 1, 2*n+1, st+n+1, lstVal+n, 1);
			if(st+n)	ans += get(1, 1, 2*n+1, 1, st+n, 0)*(lstVal-st+1);
			update(1, 1, 2*n+1, st+n+1, lstVal+n+1, 1);
		}
		seg[1][3] = true;
		seg[1][2] = 0;
		doLazy(1, 1, 2*n+1);
	}
	cout << ans << '\n';

    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:122:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |   for(int j = 1; j+1 < o[i].size(); j++)
      |                  ~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 2 ms 8284 KB Output is correct
4 Correct 2 ms 8284 KB Output is correct
5 Correct 2 ms 8368 KB Output is correct
6 Correct 3 ms 8536 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 2 ms 8284 KB Output is correct
4 Correct 2 ms 8284 KB Output is correct
5 Correct 2 ms 8368 KB Output is correct
6 Correct 3 ms 8536 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 2 ms 8360 KB Output is correct
9 Correct 3 ms 8540 KB Output is correct
10 Correct 3 ms 8576 KB Output is correct
11 Correct 4 ms 8740 KB Output is correct
12 Correct 4 ms 8540 KB Output is correct
13 Correct 3 ms 8744 KB Output is correct
14 Correct 4 ms 10588 KB Output is correct
15 Correct 4 ms 8536 KB Output is correct
16 Correct 4 ms 10768 KB Output is correct
17 Correct 3 ms 8540 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 14360 KB Output is correct
2 Correct 100 ms 15960 KB Output is correct
3 Correct 59 ms 12852 KB Output is correct
4 Correct 107 ms 16204 KB Output is correct
5 Correct 109 ms 16412 KB Output is correct
6 Correct 117 ms 16968 KB Output is correct
7 Correct 117 ms 17104 KB Output is correct
8 Correct 116 ms 16956 KB Output is correct
9 Correct 123 ms 17204 KB Output is correct
10 Correct 116 ms 16936 KB Output is correct
11 Correct 101 ms 33260 KB Output is correct

Subtask #4
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8284 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 2 ms 8284 KB Output is correct
4 Correct 2 ms 8284 KB Output is correct
5 Correct 2 ms 8368 KB Output is correct
6 Correct 3 ms 8536 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 2 ms 8360 KB Output is correct
9 Correct 3 ms 8540 KB Output is correct
10 Correct 3 ms 8576 KB Output is correct
11 Correct 4 ms 8740 KB Output is correct
12 Correct 4 ms 8540 KB Output is correct
13 Correct 3 ms 8744 KB Output is correct
14 Correct 4 ms 10588 KB Output is correct
15 Correct 4 ms 8536 KB Output is correct
16 Correct 4 ms 10768 KB Output is correct
17 Correct 3 ms 8540 KB Output is correct
18 Correct 77 ms 14360 KB Output is correct
19 Correct 100 ms 15960 KB Output is correct
20 Correct 59 ms 12852 KB Output is correct
21 Correct 107 ms 16204 KB Output is correct
22 Correct 109 ms 16412 KB Output is correct
23 Correct 117 ms 16968 KB Output is correct
24 Correct 117 ms 17104 KB Output is correct
25 Correct 116 ms 16956 KB Output is correct
26 Correct 123 ms 17204 KB Output is correct
27 Correct 116 ms 16936 KB Output is correct
28 Correct 101 ms 33260 KB Output is correct
29 Correct 111 ms 34788 KB Output is correct
30 Correct 74 ms 16724 KB Output is correct
31 Correct 147 ms 26452 KB Output is correct
32 Correct 395 ms 44164 KB Output is correct
33 Correct 164 ms 27164 KB Output is correct
34 Correct 160 ms 27684 KB Output is correct
35 Correct 99 ms 18516 KB Output is correct
36 Correct 60 ms 15952 KB Output is correct
37 Correct 78 ms 17056 KB Output is correct
38 Correct 150 ms 26796 KB Output is correct
39 Correct 147 ms 27772 KB Output is correct
40 Correct 159 ms 26788 KB Output is correct
41 Correct 149 ms 27832 KB Output is correct
42 Correct 149 ms 26704 KB Output is correct
43 Correct 179 ms 32220 KB Output is correct
44 Correct 182 ms 33888 KB Output is correct
45 Correct 180 ms 33352 KB Output is correct
46 Correct 188 ms 32596 KB Output is correct
47 Correct 192 ms 33816 KB Output is correct
48 Correct 238 ms 35668 KB Output is correct
49 Correct 263 ms 33800 KB Output is correct
50 Correct 217 ms 36100 KB Output is correct
51 Correct 228 ms 35992 KB Output is correct
52 Correct 248 ms 35928 KB Output is correct
53 Correct 239 ms 35412 KB Output is correct
54 Correct 231 ms 37460 KB Output is correct