oj.uz

Submission #569248

# Submission time Handle Problem Language Result Execution time Memory
569248 2022-05-27T06:56:26 Z knightron0 Izbori (COCI22_izbori) C++14
40 / 110
 3000 ms 31880 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define pb push_back
#define fr first
#define sc second
#define clr(a, x) memset(a, x, sizeof(a))
#define dbg(x) cout<<"("<<#x<<"): "<<x<<endl;
#define printvector(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout<<*it<<" "; cout<<endl;
#define all(v) v.begin(), v.end()
#define lcm(a, b) (a * b)/__gcd(a, b)
#define int long long int
#define printvecpairs(vec) for(auto it: vec) cout<<it.fr<<' '<<it.sc<<endl;
#define endl '\n'
#define float long double

const int MOD = 1e9 + 7;
const int INF = 2e15;
const int MAXN = 1e5 + 5;

typedef tree<
pair<int, int>,
null_type,
less<pair<int, int>>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    #endif
    int n;
    cin>>n;
    int a[n+3];
    set<int> s;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s.insert(a[i]);
    }
    int ans = 0;
    for(auto it: s){
        int p[n+3];
        for(int i=1;i<=n;i++){
            if(a[i] == it) p[i] = 1;
            else p[i] = -1;
        }
        int pref[n+3];
        pref[0] = 0;
        for(int i=1;i<=n;i++){
            pref[i] = pref[i-1] + p[i];
        }
        map<int, int> freq;
        ordered_set so;
        freq[pref[n]]++;
        so.insert({pref[n], n});
        for(int i=n;i>=1;i--){
            ans += (n-i+1)-freq[pref[i-1]]-so.order_of_key({pref[i-1], i-1});
            freq[pref[i-1]]++;
            so.insert({pref[i-1], i-1});
        }
    }
    cout<<ans<<endl;
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 232 ms 476 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 8 ms 608 KB Output is correct
10 Correct 7 ms 596 KB Output is correct
11 Correct 9 ms 588 KB Output is correct
12 Correct 7 ms 612 KB Output is correct
13 Correct 7 ms 604 KB Output is correct
14 Correct 10 ms 596 KB Output is correct
15 Correct 8 ms 604 KB Output is correct
16 Correct 7 ms 596 KB Output is correct
17 Correct 2 ms 596 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 11780 KB Output is correct
2 Correct 151 ms 15312 KB Output is correct
3 Correct 88 ms 8908 KB Output is correct
4 Correct 166 ms 15932 KB Output is correct
5 Correct 161 ms 16576 KB Output is correct
6 Correct 173 ms 17532 KB Output is correct
7 Correct 166 ms 17544 KB Output is correct
8 Correct 172 ms 17488 KB Output is correct
9 Correct 168 ms 17488 KB Output is correct
10 Correct 167 ms 17460 KB Output is correct
11 Correct 227 ms 30008 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 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 232 ms 476 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 8 ms 608 KB Output is correct
10 Correct 7 ms 596 KB Output is correct
11 Correct 9 ms 588 KB Output is correct
12 Correct 7 ms 612 KB Output is correct
13 Correct 7 ms 604 KB Output is correct
14 Correct 10 ms 596 KB Output is correct
15 Correct 8 ms 604 KB Output is correct
16 Correct 7 ms 596 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 113 ms 11780 KB Output is correct
19 Correct 151 ms 15312 KB Output is correct
20 Correct 88 ms 8908 KB Output is correct
21 Correct 166 ms 15932 KB Output is correct
22 Correct 161 ms 16576 KB Output is correct
23 Correct 173 ms 17532 KB Output is correct
24 Correct 166 ms 17544 KB Output is correct
25 Correct 172 ms 17488 KB Output is correct
26 Correct 168 ms 17488 KB Output is correct
27 Correct 167 ms 17460 KB Output is correct
28 Correct 227 ms 30008 KB Output is correct
29 Correct 236 ms 31880 KB Output is correct
30 Execution timed out 3037 ms 7756 KB Time limit exceeded
31 Halted 0 ms 0 KB -