oj.uz

Submission #673155

# Submission time Handle Problem Language Result Execution time Memory
673155 2022-12-19T20:47:05 Z KiriLL1ca Izbori (COCI22_izbori) C++17
15 / 110
 35 ms 6040 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>;



struct fen {
        vector <int> t;
        int norm;
        fen (int n = 0) : norm(n >> 1), t(n + 100) {}
        inline void upd (int i, int x) { for (i += norm; i < sz(t); i += (i & -i)) t[i] += x; }
        inline int get (int i) { int res = 0; for (i += norm; i; i -= (i & -i)) res += t[i]; return res; }
        inline int get (int l, int r) { return get(r) - get(l - 1); }
};

inline void solve () {
        int n; cin >> n;
        vector <int> a (n + 1);
        for (int i = 1; i <= n; ++i) cin >> a[i], --a[i];
        map <int, vector <int>> mp;
        for (int i = 1; i <= n; ++i) mp[a[i]].pb(i);

        const int N = n * 4 + 100;
        const int B = 1800;
        ll ans = 0;

        function <ll(ll, ll)> sum = [&] (ll l, ll r) { return 0ll; (l + r) * 1ll * (r - l + 1) / 2; };
        function <ll(ll, ll, ll)> f = [&] (ll L, ll R, ll k) {
                umin(L, k); umin(R, k);
                ll ret = 0;
                ret += (k - R) * R;
                ret += sum(0, R) + (R + 1);
                return ret;
        };

        for (auto &[_, pos] : mp) {
                if (sz(pos) > B) {
                        vector <int> c (n + 1);
                        fen t (N); t.upd(0, 1);
                        for (int i = 1; i <= n; ++i) c[i] = c[i - 1] + (a[i] == _ ? +1 : 0);
                        for (int i = 1; i <= n; ++i) {
                                ans += t.get(2 * c[i] - i - 1);
                                t.upd(2 * c[i] - i, 1);
                        }
                }
                else {
                        for (int i = 0; i < sz(pos); ++i) {
                                for (int j = i; j < sz(pos); ++j) {
                                        int c = j - i + 1;
                                        int len = pos[j] - pos[i] + 1;
                                        int k = 2 * c - len - 1;
                                        int L = (i ? pos[i] - pos[i - 1] - 1 : pos[i] - 1);
                                        int R = (j + 1 < sz(pos) ? pos[j + 1] - pos[j] - 1 : n - pos[j]);
                                        ans += f(L, R, k);
                                }
                        }
                }
        }
        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;
}

Compilation message

Main.cpp: In constructor 'fen::fen(int)':
Main.cpp:33:13: warning: 'fen::norm' will be initialized after [-Wreorder]
   33 |         int norm;
      |             ^~~~
Main.cpp:32:22: warning:   'std::vector<int> fen::t' [-Wreorder]
   32 |         vector <int> t;
      |                      ^
Main.cpp:34:9: warning:   when initialized here [-Wreorder]
   34 |         fen (int n = 0) : norm(n >> 1), t(n + 100) {}
      |         ^~~
Main.cpp: In lambda function:
Main.cpp:51:96: warning: statement has no effect [-Wunused-value]
   51 |         function <ll(ll, ll)> sum = [&] (ll l, ll r) { return 0ll; (l + r) * 1ll * (r - l + 1) / 2; };
      |                                                                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4120 KB Output is correct
2 Correct 23 ms 5176 KB Output is correct
3 Correct 13 ms 3132 KB Output is correct
4 Correct 24 ms 5448 KB Output is correct
5 Correct 26 ms 5672 KB Output is correct
6 Correct 29 ms 5960 KB Output is correct
7 Correct 35 ms 5968 KB Output is correct
8 Correct 27 ms 6016 KB Output is correct
9 Correct 28 ms 6040 KB Output is correct
10 Correct 30 ms 5972 KB Output is correct
11 Correct 18 ms 5848 KB Output is correct

Subtask #4
0 / 70.0

# Verdict Execution time Memory 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 -