제출 #1260720

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1260720		zertinii	Infinite Race (EGOI24_infiniterace2)	C++20	0 / 100	16 ms	12868 KiB

Main

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define vecint vector <int>
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define L(i, j, k) for(int i = (j); i <= (k); i++)
/*#pragma optimize ("g",on)
#pragma GCC optimize ("inline")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("03")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")
#pragma comment(linker, "/stack:200000000")*/
const int N = 4e5 + 1;
const int mod = 1e9 + 7;
using namespace std;
//using namespace __gnu_pbds;
//template <typename T>
//using o_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
/*struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};*/
void solve(){
    int n, q;
    cin >> n >> q;
    vecint mp(n), f(n), l(n), mp1(n);
    vecint a(q + 1);
    vecint g[n];
    L(i, 1, q) {
        int x;
        cin >> x;
        a[i] = x;
        if (x > 0) {
            mp[x]++;
            if (!f[x]) {
                f[x] = i;
            }
        }
        else {
            g[-x].pb(i);
            mp1[-x]++;
        }
    }
    R(i, q, 1) {
        if ( a[i] > 0 ) {
            if ( !l[a[i]] ) {
                l[a[i]] = i;
            }
        }
    }
    int ans = 0;
    L(i, 1, n - 1) {
        if (mp[i] > 1) {
            if (mp1[i] == 0) {
                ans += mp[i] - 1;
                continue;
            }
            int x = f[i], y = l[i];
            int l = 0, r = g[i].size() - 1;
            while (r >= l) {
                int mid = l + r >> 1;
                if ( g[i][mid] >= x) {
                    r = mid - 1;
                }
                else {
                    l = mid + 1;
                }
            }
            int ll = r + 1, rr = 0;
            l = 0, r = g[i].size() - 1;
            while (r >= l) {
                int mid = l + r >> 1;
                if (g[i][mid] <= y) {
                    l = mid + 1;
                }
                else {
                    r = mid - 1;
                }
            }
            rr = l - 1;
            int X = rr - ll + 1;
            ans += max(0ll,  mp[i] - X - 1 );
        }
    }
    cout << ans;
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("ohwow.txt", "r", stdin);
    //freopen("superbull.out", "w", stdout);
    int tt = 1;
    //cin >> tt;
    while(tt--) {
        solve();
    }
}

• Subtask 1: 0 / 29
• Subtask 2: 0 / 34
• Subtask 3: 0 / 22
• Subtask 4: 0 / 15