oj.uz

Submission #795736

# Submission time Handle Problem Language Result Execution time Memory
795736 2023-07-27T13:52:09 Z NguyenKhang Izbori (COCI22_izbori) C++17
110 / 110
 2707 ms 15280 KB 
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("bmi,bmi2,lzcnt,popcnt")
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
//#pragma expected_value
//#pragma isolated_call
//#pragma disjoint

#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

//using namespace __gnu_pbds;
using namespace std;

#define int long long
//#define double long double
#define Fi first
#define Se second
#define Rep(i,a,b) for (int i=a;i<=b;++i)
#define Repu(i,b,a) for (int i=b;i>=a;--i)
#define pb push_back
#define ms(a,i) memset(a,i,sizeof(a))
#define sz size()
#define mp make_pair
#define endl '\n'
#define sef setprecision(6)<<fixed
#define cer cout<<"cak"<<endl;

typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<double> va;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<va> vva;

//const double EPS=1e-9;
const double PI=acos(-1);
const long long oo=1e18;
const int MN=2e5+5;
const int mod=1e9+7;

using cd=complex<double>;

//typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> index_set;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int cunt = 400;

int n;
int a[MN];

vi s[MN];

int cnt;

int ans = 0;

int type[MN];

void compress() {
	vii v; v.pb(mp(0,0));
	Rep(i,1,n) v.pb(mp(a[i],i));
	sort(v.begin(),v.end());

	Rep(i,1,n) {
		if(v[i].Fi != v[i-1].Fi) ++cnt;
		a[v[i].Se] = cnt;
		s[cnt].pb(v[i].Se);
	}
}

void light() {
	Rep(i,1,n) {
		int mx = 0;
		Rep(j,i,min(i+cunt,n)) {
			int color = a[j];
			if(type[color] == 0) continue;
			int temp = lower_bound(s[color].begin(), s[color].end(), j) - lower_bound(s[color].begin(), s[color].end(), i) + 1;

			if(temp > mx) mx = temp;
			if(mx*2 > j-i+1) ++ans;
		}
	}
}

struct Fenwick_tree {
	int b[2*MN];

	void clear() {
		Rep(i,1,2*MN) b[i] = 0;
	}

	void updatePoint(int u,int val) {
		while(u<2*MN) {
			b[u] += val;
			u += (u&(-u));
		}
	}

	int getPrefix(int u) {
		if(u <= 0) return 0;
		int ans=0;
		while(u) {
			ans += b[u];
			u -= (u&(-u));
		}
		return ans;
	}
};

Fenwick_tree bit;

void heavy(int color) {
	bit.clear();
	bit.updatePoint(n+1, 1);
	int pre = 0;

	Rep(i,1,n) {
		if(a[i] == color) ++pre;
		ans += bit.getPrefix(2*pre - i + n);
		bit.updatePoint(2*pre - i + n + 1, 1);
	}
}

signed main() {
  	//freopen(".inp","r",stdin); freopen(".out","w",stdout);
  	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin>>n; 
	Rep(i,1,n) cin>>a[i];
	compress();

	// light
	Rep(i,1,cnt) {
		if(s[i].sz <= cunt) type[i] = 1;
	}
	light();

	// heavy
	Rep(i,1,cnt) {
		if(type[i]) continue;
		heavy(i);
	}

	cout<<ans;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:138:14: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  138 |   if(s[i].sz <= cunt) type[i] = 1;
      |      ~~~~~~~~^~~~~~~
Main.cpp: In function 'void heavy(long long int)':
Main.cpp:90:22: warning: iteration 400009 invokes undefined behavior [-Waggressive-loop-optimizations]
   90 |   Rep(i,1,2*MN) b[i] = 0;
      |                 ~~~~~^~~
Main.cpp:18:34: note: within this loop
   18 | #define Rep(i,a,b) for (int i=a;i<=b;++i)
......
   90 |   Rep(i,1,2*MN) b[i] = 0;
      |       ~~~~~~~~                    
Main.cpp:90:3: note: in expansion of macro 'Rep'
   90 |   Rep(i,1,2*MN) b[i] = 0;
      |   ^~~
In member function 'void Fenwick_tree::clear()',
    inlined from 'void heavy(long long int)' at Main.cpp:114:11:
Main.cpp:90:22: warning: 'void* __builtin_memset(void*, int, long unsigned int)' forming offset [3200080, 3200087] is out of the bounds [0, 3200080] of object 'bit' with type 'Fenwick_tree' [-Warray-bounds]
   90 |   Rep(i,1,2*MN) b[i] = 0;
      |                 ~~~~~^~~
Main.cpp: In function 'void heavy(long long int)':
Main.cpp:111:14: note: 'bit' declared here
  111 | Fenwick_tree bit;
      |              ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 4 ms 5056 KB Output is correct
4 Correct 4 ms 5044 KB Output is correct
5 Correct 4 ms 4948 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 4 ms 5056 KB Output is correct
4 Correct 4 ms 5044 KB Output is correct
5 Correct 4 ms 4948 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Correct 4 ms 5120 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 31 ms 5128 KB Output is correct
10 Correct 28 ms 5132 KB Output is correct
11 Correct 27 ms 5076 KB Output is correct
12 Correct 28 ms 5076 KB Output is correct
13 Correct 28 ms 5048 KB Output is correct
14 Correct 28 ms 5064 KB Output is correct
15 Correct 27 ms 5148 KB Output is correct
16 Correct 27 ms 5076 KB Output is correct
17 Correct 4 ms 8276 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 11256 KB Output is correct
2 Correct 130 ms 11848 KB Output is correct
3 Correct 61 ms 10240 KB Output is correct
4 Correct 106 ms 11912 KB Output is correct
5 Correct 107 ms 12080 KB Output is correct
6 Correct 115 ms 12324 KB Output is correct
7 Correct 118 ms 12368 KB Output is correct
8 Correct 139 ms 12312 KB Output is correct
9 Correct 114 ms 12308 KB Output is correct
10 Correct 117 ms 12312 KB Output is correct
11 Correct 104 ms 13288 KB Output is correct

Subtask #4
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 4 ms 5056 KB Output is correct
4 Correct 4 ms 5044 KB Output is correct
5 Correct 4 ms 4948 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Correct 4 ms 5120 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 31 ms 5128 KB Output is correct
10 Correct 28 ms 5132 KB Output is correct
11 Correct 27 ms 5076 KB Output is correct
12 Correct 28 ms 5076 KB Output is correct
13 Correct 28 ms 5048 KB Output is correct
14 Correct 28 ms 5064 KB Output is correct
15 Correct 27 ms 5148 KB Output is correct
16 Correct 27 ms 5076 KB Output is correct
17 Correct 4 ms 8276 KB Output is correct
18 Correct 80 ms 11256 KB Output is correct
19 Correct 130 ms 11848 KB Output is correct
20 Correct 61 ms 10240 KB Output is correct
21 Correct 106 ms 11912 KB Output is correct
22 Correct 107 ms 12080 KB Output is correct
23 Correct 115 ms 12324 KB Output is correct
24 Correct 118 ms 12368 KB Output is correct
25 Correct 139 ms 12312 KB Output is correct
26 Correct 114 ms 12308 KB Output is correct
27 Correct 117 ms 12312 KB Output is correct
28 Correct 104 ms 13288 KB Output is correct
29 Correct 111 ms 15280 KB Output is correct
30 Correct 129 ms 7228 KB Output is correct
31 Correct 275 ms 9244 KB Output is correct
32 Correct 745 ms 14736 KB Output is correct
33 Correct 330 ms 9548 KB Output is correct
34 Correct 300 ms 9784 KB Output is correct
35 Correct 194 ms 8144 KB Output is correct
36 Correct 110 ms 6992 KB Output is correct
37 Correct 137 ms 7276 KB Output is correct
38 Correct 134 ms 12184 KB Output is correct
39 Correct 138 ms 12192 KB Output is correct
40 Correct 172 ms 12140 KB Output is correct
41 Correct 135 ms 12164 KB Output is correct
42 Correct 135 ms 12208 KB Output is correct
43 Correct 185 ms 13564 KB Output is correct
44 Correct 179 ms 13524 KB Output is correct
45 Correct 181 ms 13548 KB Output is correct
46 Correct 194 ms 13556 KB Output is correct
47 Correct 183 ms 13708 KB Output is correct
48 Correct 1439 ms 12232 KB Output is correct
49 Correct 1430 ms 12236 KB Output is correct
50 Correct 633 ms 12396 KB Output is correct
51 Correct 639 ms 12396 KB Output is correct
52 Correct 2707 ms 12208 KB Output is correct
53 Correct 2505 ms 12060 KB Output is correct
54 Correct 1446 ms 12196 KB Output is correct