oj.uz

Submission #637092

# Submission time Handle Problem Language Result Execution time Memory
637092 2022-08-31T13:19:09 Z epicci23 Grudanje (COCI19_grudanje) C++17
70 / 70
 721 ms 26572 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 980 KB Output is correct
2 Correct 5 ms 980 KB Output is correct
3 Correct 5 ms 1096 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 968 KB Output is correct
2 Correct 5 ms 1052 KB Output is correct
3 Correct 5 ms 972 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1108 KB Output is correct
2 Correct 6 ms 1096 KB Output is correct
3 Correct 5 ms 980 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 698 ms 26552 KB Output is correct
2 Correct 294 ms 26436 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 26572 KB Output is correct
2 Correct 371 ms 26444 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 712 ms 26536 KB Output is correct
2 Correct 721 ms 26572 KB Output is correct
3 Correct 283 ms 26444 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 717 ms 26572 KB Output is correct
2 Correct 706 ms 26548 KB Output is correct
3 Correct 306 ms 26428 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 673 ms 26532 KB Output is correct
2 Correct 697 ms 26556 KB Output is correct
3 Correct 285 ms 26444 KB Output is correct