oj.uz

답안 #672735

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
672735 2022-12-17T19:43:48 Z KiriLL1ca Izbori (COCI22_izbori) C++17
0 / 110
 9 ms 3328 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pw(x) (1ll << x)
#define sz(x) (int)((x).size())
#define pb push_back
#define endl '\n'
#define mp make_pair
#define vec vector

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef unsigned long long ull;

template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T>
using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

#define int long long

inline void solve () {
        int n; cin >> n;
        vector <int> a (n);
        for (auto &i : a) cin >> i;
        map <int, vector <int>> mp;
        for (int i = 0; i < n; ++i) mp[a[i]].pb(i);
        const int B = 1000;
        ll ans = 0;

        function <ll(int, int)> sum = [&] (int l, int r) { return (l + r) * 1ll * (r - l + 1) / 2; };
        function <ll(int, int, int)> f = [&] (int lx, int ly, int z) {
                umin(lx, z); umin(ly, z);
                ll res = 0;
                int q = z - ly;
                res += max(0ll, q * ly);
                res += max(0ll, sum(z - ly + 1, lx));
                res += min(z, ly);
                return res;
        };

        for (auto &[_, pos] : mp) {
                if (sz(pos) <= B) {
                        for (int i = 0; i < sz(pos); ++i) {
                                for (int j = i; j < sz(pos); ++j) {
                                        int need = (pos[j] - pos[i] + 1) / 2 + 1;
                                        if (need > j - i + 1) continue;

                                        int lft, rgt;
                                        if (!i) lft = pos[i];
                                        else lft = pos[i] - pos[i - 1] - 1;

                                        if (j + 1 == sz(pos)) rgt = n - pos[j] - 1;
                                        else rgt = pos[j + 1] - pos[j];

                                        int can = (j - i + 1) * 2 - 1 - pos[j] + pos[i] - 1;
                                        ans += f(lft, rgt, can) + 1;
                                }
                        }
                }
                else {

                }
        }
        cout << ans;
}

signed main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        #ifdef LOCAL
                freopen("input.txt", "r", stdin);
                freopen("output.txt", "w", stdout);
        #endif
        int t = 1; // cin >> t;
        while (t--) solve();
        return 0;
}

/// n <= 300

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 3328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -