Submission #696944

#	Time	Username	Problem	Language	Result	Execution time	Memory
696944		tamthegod	Izbori (COCI22_izbori)	C++17	110 / 110	609 ms	15800 KiB

Main

// Make the best become better
// No room for laziness
#include<bits/stdc++.h>

#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 2e5 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int n, a[maxN];
vector<int> pos[maxN];
const int block_size = 1000;
int b[maxN];
int bit[maxN * 2];
void update(int pos)
{
    while(pos <= 2 * n)
    {
        bit[pos]++;
        pos += pos & -pos;
    }
}
int get(int pos)
{
    int res = 0;
    while(pos)
    {
        res += bit[pos];
        pos -= pos & -pos;
    }
    return res;
}
void ReadInput()
{
    cin >> n;
    vector<int> vc;
    for(int i=1; i<=n; i++)
    {
        cin >> a[i];
        vc.pb(a[i]);
    }
    sort(vc.begin(), vc.end());
    vc.erase(unique(vc.begin(), vc.end()), vc.end());
    for(int i=1; i<=n; i++)
        a[i] = upper_bound(vc.begin(), vc.end(), a[i]) - vc.begin();
    for(int i=1; i<=n; i++)
        pos[a[i]].pb(i);
}
int f(int l, int r)
{
    return (r + l) * (r - l + 1) / 2;
}
int res = 0;
void Cal1(int val)
{
    for(int i=0; i<pos[val].size(); i++)
    {
        for(int j=i; j>=0; j--)
        {
           // i = 4, j = 2;
            int r = pos[val][i], l = pos[val][j];
            int s = 2 * (i - j + 1) - (r - l + 1);
            if(s <= 0) continue;
            int last1 = j ? pos[val][j - 1] : 0;
            int last2 = i == pos[val].size() - 1 ? n + 1 : pos[val][i + 1];
            int left = s - 1;
            int t1 = l - last1 - 1, t2 = last2 - r - 1;
            t1 = min(t1, left);
            t2 = min(t2, left);
           // cout << t2;exit(0);
            /// cal 0 <= x1 <= t1, 0 <= x2 <= t2, x1 + x2 <= left
           // cout << s;exit(0);
            if(t1 + t2 <= left) res += (t1 + 1) * (t2 + 1);
            else
            {
                res += (t2 + 1) * (left - t2 + 1);
                int t = min(t1 - (left - t2 + 1), t2 - 1);
                res += f(t2 - t, t2);
            }
           //cout << res;exit(0);
        }
    }
}
void Cal2(int val)
{
    for(int i=1; i<=n; i++)
        b[i] = b[i - 1] + (a[i] == val ? 1 : -1);
    memset(bit, 0, sizeof bit);
    update(n);
    for(int i=1; i<=n; i++)
    {
        res += get(b[i] + n - 1);
        update(b[i] + n);
    }
}
void Solve()
{
    for(int i=1; i<=n; i++)
    {
        if(pos[i].empty()) continue;
        if(pos[i].size() <= block_size) Cal1(i);
        else Cal2(i);
    }
    cout << res;
}
int32_t main()
{
   // freopen("sol.inp", "r", stdin);
   // freopen("sol.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}

Compilation message (stderr)

Main.cpp: In function 'void Cal1(long long int)':
Main.cpp:63:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i=0; i<pos[val].size(); i++)
      |                  ~^~~~~~~~~~~~~~~~
Main.cpp:72:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             int last2 = i == pos[val].size() - 1 ? n + 1 : pos[val][i + 1];
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~

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