Submission #445752

#	Time	Username	Problem	Language	Result	Execution time	Memory
445752		Chy_Chy	Grudanje (COCI19_grudanje)	C++14	14 / 70	2119 ms	353436 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;}


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

struct segtree {
    int size;

    vector<int> val;
    set<int> *segment;
    void init(int n) {
        size = 1;

        while (size < n) {
            size *= 2;
        }
        val.assign(2 * size, 0);
        segment = new set<int>[2 * size];
    }



    void build(vector<int> &a, int node, int tl, int tr) {

        if ((tr - tl) == 1) {
            if (tl < a.size()) {

                segment[node].insert(a[tl]);

            }
            return;
        }

        int tm = tl + (tr - tl) / 2;
        build(a, 2 * node + 1, tl, tm);
        build(a, 2 * node + 2, tm, tr);


        segment[node].insert(segment[2 * node + 1].begin(), segment[2 * node + 1].end());
        segment[node].insert(segment[2 * node + 2].begin(), segment[2 * node + 2].end());
    }

    void build(vector<int> &a) {
        build(a, 0, 0, size);
    }

    set<int> query(int ql, int qr, int node, int tl, int tr) {

        set<int> lft, rht, res;
        if (tl >= qr || tr <= ql) { // out of range
            return res;
        }
        if (tl >= ql && tr <= qr) { // completely inside the query range
            return segment[node];
        }

        int tm = tl + (tr - tl) / 2;

        // int v1 = query(ql, qr, 2 * node + 1, tl, tm);
        // int v2 = query(ql, qr, 2 * node + 2, tm, tr);
        lft = query(ql, qr, 2 * node + 1, tl, tm);
        rht = query(ql, qr, 2 * node + 2, tm, tr);

        res.insert(lft.begin(), lft.end());
        res.insert(rht.begin(), rht.end());
        // return merge(v1, v2);

        return res;
    }
    set<int> query(int ql, int qr) {
        return query(ql, qr, 0, 0, size);
    }
};
vi idx;
bool chk(int x) {
    // debug(x);
    segtree st;

    vi tmp;
    int cnt = 100;
    for (int i = 0; i < n; i++) {
        int x = s[i] - 'a';
        tmp.pb(x);
    }
    for (int i = 0; i <= x; i++) {
        tmp[idx[i]] = cnt;
        cnt++;
    }

    // for (int ele : tmp) {
    //     cout << ele << endl;
    // }
    st.init(n);
    st.build(tmp);

    for (int i = 0; i < q; i++) {
        int l = subs[i].ff;
        int r = subs[i].ss;
        set<int> res = st.query(l , r + 1);
        // for (auto ele : res) {
        //     cout << ele << "#";
        // }
        // cout << endl;

        // debug(l);
        // debug(r);
        // debug(res.size());
        // debug(r - l + 1);
        if (res.size() != (r - l + 1)) {
            return false;
        }
    }
    return true;
}

void KhelaFinal() {
    cin >> s;
    n = (int)s.size();


    cin >> q;
    for (int i = 0; i < q; i++) {
        int x, y; cin >> x >> y;
        subs.pb({x - 1, y - 1});
    }

    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        idx.pb(x - 1);
    }
    vi tmp;
    for (int i = 0; i < n; i++) {
        int x = s[i] - 'a';
        tmp.pb(x);
    }

    segtree st;
    st.init(n);
    st.build(tmp);

    bool ok = 1;

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

        set<int> res = st.query(l, r + 1);
        if (res.size() != (r - l + 1)) {
            ok = 0;
            break;
        }
    }
    if (ok) {
        cout << 0 << endl;
        return;
    }
    int lo = 0;
    int hi = n - 1;
    int ans;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        // debug(mid);
        if (chk(mid)) {
            hi = mid - 1;
            ans = mid;
        }
        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 member function 'void segtree::build(std::vector<long long int>&, long long int, long long int, long long int)':
grudanje.cpp:93:20: 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]
   93 |             if (tl < a.size()) {
      |                 ~~~^~~~~~~~~~
grudanje.cpp: In function 'bool chk(long long int)':
grudanje.cpp:176:24: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  176 |         if (res.size() != (r - l + 1)) {
      |             ~~~~~~~~~~~^~~~~~~~~~~~~~
grudanje.cpp: In function 'void KhelaFinal()':
grudanje.cpp:215:24: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  215 |         if (res.size() != (r - l + 1)) {
      |             ~~~~~~~~~~~^~~~~~~~~~~~~~
grudanje.cpp:239:19: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  239 |     cout << ans + 1 << endl;
      |                   ^

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