Submission #446499

#	Time	Username	Problem	Language	Result	Execution time	Memory
446499		Chy_Chy	Grudanje (COCI19_grudanje)	C++14	70 / 70	719 ms	26068 KiB

grudanje

#include<bits/stdc++.h>
using namespace std;

#include<ext/pb_ds/assoc_container.hpp> // common file
#include<ext/pb_ds/tree_policy.hpp> // including tree_order_statistics_node_update

using namespace __gnu_pbds;


#define int             long long
#define pb              push_back
#define ppb             pop_back
#define pf              push_front
#define ppf             pop_front
#define all(x)          (x).begin(), (x).end()
#define uniq(v)         (v).erase(unique(all(v)), (v).end())
#define sz(x)           (int)((x).size())
#define ff              first
#define ss              second
#define rep(i, a, b)    for(int i = a; i <= b; i++)
#define mem1(a)         memset(a, -1, sizeof(a))
#define mem0(a)         memset(a, 0, sizeof(a))
#define endl            "\n"
#define debug(x)        cerr << #x << " == " << (x) << '\n';
#define YES             cout << "YES\n"
#define NO              cout << "NO\n"
#define nn              "\n"

// bit manipulation
#define SetBit(x, k)    (x |= (1LL << k))
#define ClearBit(x, k)  (x &= ~(1LL << k))
#define CheckBit(x, k)  (x & (1LL << k))


typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;

#define ordered_set tree<int, null_type, less<int> , rb_tree_tag, tree_order_statistics_node_update>

const long long INF = 1e18;
const int32_t M = 1e9 + 7;
const int32_t MM = 998244353;


int binpow(int a, int b) {
    int res = 1;
    while (b > 0) {
        if (b & 1) {
            res = a * res;
        }
        a = a * a;
        b >>= 1;
    }
    return res;
}


void fast_io()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
}
int gcd(int a, int b) {if (b == 0) return a; return gcd(b, a % b);}
int lcm(int a, int b) {return a / gcd(a, b) * b;}


string s;
int n;
vpii subs;
vi snowballs;
int q;

bool chk(int x) {
    int cum[26][n];
    for (int i = 0; i < 26; i++) {
        for (int j = 0; j < n; j++) {
            cum[i][j] = 0;
        }
    }

    string tmp = s;

    for (int i = 0; i <= x; i++) {
        tmp[snowballs[i]] = '*';
    }

    for (int i = 0; i < n; i++) {
        if (tmp[i] >= 'a' && tmp[i] <= 'z') {
            int al = tmp[i] - 'a';
            cum[al][i] = 1;
        }
    }
    for (int i = 0; i < 26; i++) {
        for (int j = 1; j < n; j++) {
            cum[i][j] += cum[i][j - 1];
        }
    }

    for (int i = 0; i < q; i++) {
        int l = subs[i].ff;
        int r = subs[i].ss;

        for (int j = 0; j < 26; j++) {
            int occ;
            if (l == 0) {
                occ = cum[j][r];
            }
            else {
                occ = cum[j][r] - cum[j][l - 1];
            }
            if (occ > 1) {
                return false;
            }
        }
    }
    return true;
}
void KhelaFinal() {

    cin >> s;
    n = s.size();
    cin >> q;
    for (int i = 0; i < q; i++) {
        int l, r; cin >> l >> r;
        subs.pb({l - 1, r - 1});
    }
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        snowballs.pb(x - 1);
    }

    if (chk(-1)) {
        cout << 0 << endl;
        return;
    }
    int lo = 0;
    int hi = n - 1;
    int ans;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (chk(mid)) {
            ans = mid;
            hi = mid - 1;
        }
        else {
            lo = mid + 1;
        }
    }

    cout << ans + 1 << endl;



}

signed main()
{
    fast_io();
//#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//#endif
    int t = 1;

    // cin >> t;


    while (t--) {

        KhelaFinal();


    }
    return 0;


}

Compilation message (stderr)

grudanje.cpp: In function 'void KhelaFinal()':
grudanje.cpp:151:19: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  151 |     cout << ans + 1 << endl;
      |                   ^

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 7 / 7
• Subtask 5: 7 / 7
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7