Submission #284473

#	Time	Username	Problem	Language	Result	Execution time	Memory
284473		PedroBigMan	Grudanje (COCI19_grudanje)	C++14	70 / 70	55 ms	5808 KiB

grudanje

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=a; i<b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 5000000

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll N; string t; cin>>t; N=t.size(); ll Q; cin>>Q;
    vector<pl> s; pl cur; REP(i,0,Q) {cin>>cur.ff>>cur.ss; cur.ff--; cur.ss--; s.pb(cur);}
    sort(whole(s));
    vector<ll> max_end; ll me=0;
    REP(i,0,Q) {me=max(me,s[i].ss); max_end.pb(me);}
    vector<ll> p; In(p,N);
    vector<set<ll> > pos; set<ll> xx; REP(i,0,26) {pos.pb(xx);}
    set<ll>::iterator it;  pl cur1; pl cur2;
    REP(i,0,N) {p[i]--;}
    for(ll i=N-1;i>=0;i--)
    {
        ll val = (ll) (t[p[i]]-'a');
        cur1=mp(-1,-1); cur2=mp(-1,-1);
        pos[val].insert(p[i]);
        it = pos[val].find(p[i]); 
        if(it!=pos[val].begin()) {it--; cur1=mp(*it,p[i]); it++;}
        it++; if(it!=pos[val].end()) {cur2=mp(p[i],*it); it--;}
        if(cur1.ff!=-1)
        {
            ll ind = (ll) (upper_bound(whole(s),mp(cur1.ff,INF))-s.begin()) -1;
            if(ind>=0 && max_end[ind]>=cur1.ss) {cout<<i+1<<endl; return 0;}
        }
        if(cur2.ff!=-1)
        {
            ll ind = (ll) (upper_bound(whole(s),mp(cur2.ff,INF))-s.begin())-1;
            if(ind>=0 && max_end[ind]>=cur2.ss) {cout<<i+1<<endl; return 0;}
        }
    }
    cout<<0<<endl;
    return 0;
}

• 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