Submission #696937

#	Time	Username	Problem	Language	Result	Execution time	Memory
696937		tamthegod	Izbori (COCI22_izbori)	C++17	25 / 110	17 ms	9308 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 = 2000;
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)
{

}
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:43: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]
   43 |     for(int i=0; i<pos[val].size(); i++)
      |                  ~^~~~~~~~~~~~~~~~
Main.cpp:52: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]
   52 |             int last2 = i == pos[val].size() - 1 ? n + 1 : pos[val][i + 1];
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~

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