Submission #1235521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235521		BuiDucManh123	Izbori (COCI22_izbori)	C++20	15 / 110	94 ms	44268 KiB

Main

#include <bits/stdc++.h>
#define int ll
#define it int
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define taskname ""
using namespace std;
int a[200009], n, i, m, t, ans, bua;
map<int, it> cnt[200009][2];
set<int> st;
vector<int> v[2][200009];
void solve(int id, int k){
    int ma = 250005, res = 0, mi = ma - v[id][k][0] + 1, hehe = mi;
    for(i = 0; i < v[id][k].size() - 1; i++){
        int q = (v[id][k][i] - id) * 2 + id;
        if(a[q] == k){
        mi = min(mi, hehe);
        if(hehe <= ma) ans += cnt[k][id][hehe] + 1;
        else ans += cnt[k][id][hehe];
        }
        if(a[q] == a[q + 1]){
            if(hehe <= ma) res += cnt[k][id][hehe] + 1;
            else res += cnt[k][id][hehe];
            hehe++;
        }
        cnt[k][id][hehe]++;
        ans += res * 2;
        if(q + 1 == n) ans -= res;
        t = min(hehe - mi, v[id][k][i + 1] - v[id][k][i] - 1);
        bua = hehe - (v[id][k][i + 1] - v[id][k][i] - 1);
        while(t--){
            hehe--;
            if(hehe <= ma) res -= cnt[k][id][hehe] + 1;
            else res -= cnt[k][id][hehe];
            ans += res * 2;
            if(n % 2 != id && hehe == bua && i == v[id][k].size() - 2) ans -= res;
            cnt[k][id][hehe]++;
        }
        hehe = bua;
        mi = min(mi, hehe);
    }
    if(n % 2 == id && a[n] == k){
        if(hehe <= ma) ans += cnt[k][id][hehe] + 1;
        else ans += cnt[k][id][hehe];
    }
}
int32_t main() {
	if (fopen(taskname".inp","r")) {
		freopen(taskname".inp","r",stdin);
		freopen(taskname".out","w",stdout);
	}
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
    cin >> n;
    for(i = 1; i <= n; i++){
        cin >> a[i];
        st.insert(a[i]);
    }
    for(i = 1; i < n; i ++){
        v[i % 2][a[i]].pb(i / 2 + i % 2);
        if(a[i] != a[i + 1]) v[i % 2][a[i + 1]].pb(i / 2 + i % 2);
    }
    for(auto x : st){
        v[1][x].pb(n / 2 + 1);
        v[0][x].pb((n + 1) / 2);
    }
    for(auto x : st){
        solve(0, x);
        solve(1, x);
    }
    cout << ans;
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:54:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |                 freopen(taskname".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:55:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |                 freopen(taskname".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 15 / 15
• Subtask 4: 0 / 70