Submission #637092

#	Time	Username	Problem	Language	Result	Execution time	Memory
637092		epicci23	Grudanje (COCI19_grudanje)	C++17	70 / 70	721 ms	26572 KiB

grudanje

#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define endl "\n" 
#define MOD 1000000007
#define int long long
#define double long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define what_is(x) cerr << #x << " is " << x << endl;
const int N=200005;
const long long INF = LLONG_MAX;
const int INF2=(int)1e18;
const int LOG=20;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
typedef priority_queue<pii,vector<pii>,greater<pii>> min_pq;
typedef priority_queue<pii> max_pq;
typedef long long ll;
//sunlari dusun//
/*
 * kodu kisaltcak  fonksiyon
 * cevaba binary search ya da normal bs
 * segment tree / sparse table
 * stack
 * teklik ciftlik
 * precomputation
 * EN ONEMLISI OVERKILLEME
 * edge case dusun
 * constraintlere bak
 * indisleri kontrol et 
 * dp
 * greedy
 * sorting
 * dfs bfs
 * sieve
*/
void solve()
{
   string s;
   cin >> s;
   int n=sz(s);
   int q;
   cin >>q;
   vector<pii> v(n+1);
   for(int i=1;i<=q;i++)
   {
     int a,b;
     cin >> a >> b;
     a--;
     b--;
     v[i]={a,b};
   }
   int poz[n+1];
   for(int i=1;i<=n;i++)
   {
    cin >> poz[i];
    poz[i]--;
   }
   int l=0,r=n;
   while(l<r)
   {
    int m=(l+r)/2;
    string cur=s;
    for(int i=1;i<=m;i++) cur[poz[i]]='*';

    int cnt[28][n+2];
    memset(cnt,0,sizeof(cnt));

    for(int i=0;i<n;i++) if(cur[i]!='*') cnt[cur[i]-'a'][i]++;

    for(int i=0;i<28;i++)
        for(int j=1;j<n;j++)
          cnt[i][j]+=cnt[i][j-1];

    bool ok=1;
    for(int i=1;i<=q;i++)
    {
        for(int j=0;j<28;j++)
        {
           int res=cnt[j][v[i].ss]-(v[i].ff==0 ? 0 : cnt[j][v[i].ff-1]);
           if(res>=2)
           {
             ok=0;
             break;
           }
        }
    }
    if(ok) r=m;
    else l=m+1;
   }
   cout << l << endl;
}

int32_t main(){
   

     cin.tie(0); ios::sync_with_stdio(0);
     cout << fixed <<  setprecision(15);
 int t=1;//cin>> t;
 
 while(t--) solve();
 
 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