Submission #333560

#	Time	Username	Problem	Language	Result	Execution time	Memory
333560		mohamedsobhi777	Martian DNA (BOI18_dna)	C++14	100 / 100	118 ms	19820 KiB

dna

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")

using namespace std;
using namespace __gnu_pbds;

#define vi vector<int>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define forn(i, n) for (int i = 0; i < n; ++i)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define uni(_) unique(_)
#define lb lower_bound
#define ub upper_bound
#define si set<int>
#define ms multiset<int>
#define qi queue<int>
#define pq prioriry_queue<int>

using ll = long long;
using ld = long double;

const int N = 2e5 + 7000;
const ll mod = 1e9 + 7;
const ll inf = 2e18;

auto ra = [] {char *p = new char ; delete p ; return ll(p) ; };
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count() * (ra() | 1));
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> os;

int n, k, r;
int a[N];
int R[N];
int sz[N];
vector<int> adj[N];

int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        //freopen("in.in", "r", stdin);
        cin >> n >> k >> r;
        for (int i = 0; i < n; ++i)
        {
                cin >> a[i];
                adj[a[i]].push_back(i);
        }
        for (int i = 0; i < r; ++i)
        {
                int x, y;
                cin >> x >> y;
                R[x] = y;
        }
        int bad = r;
        int ans = 1e9;
        set<int> st;
        for (int i = 0; i < n; ++i)
        {
                ++sz[a[i]];
                if (R[a[i]] == sz[a[i]])
                {
                        --bad;
                        st.insert(adj[a[i]][0]);
                }
                else if (sz[a[i]] > R[a[i]] && R[a[i]])
                {
                        st.erase(adj[a[i]][sz[a[i]] - R[a[i]] - 1]);
                        st.insert(adj[a[i]][sz[a[i]] - R[a[i]]]);
                }
                if (bad == 0)
                        ans = min(ans, i - (*st.begin()) + 1);
        }
        if (ans == 1e9)
                cout << "impossible";
        else
                cout << ans;
        return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 28 / 28
• Subtask 4: 32 / 32