Submission #748264

#	Time	Username	Problem	Language	Result	Execution time	Memory
748264		Trunkty	Grudanje (COCI19_grudanje)	C++14	70 / 70	537 ms	169248 KiB

grudanje

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll

string s;
int n,q;
vector<vector<int>> query;
int arr[100005];
int pref[100005][205];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> s;
    n = s.length();
    cin >> q;
    for(int i=1;i<=q;i++){
        int a,b;
        cin >> a >> b;
        query.push_back({a,b});
    }
    for(int i=1;i<=n;i++){
        int a;
        cin >> a;
        arr[a] = i;
    }
    int low=0,high=n-1;
    while(low!=high){
        int mid = (low+high)/2;
        for(int i=1;i<=n;i++){
            for(int j='a';j<='z';j++){
                pref[i][j] = pref[i-1][j];
            }
            if(arr[i]>mid){
                pref[i][s[i-1]]++;
            }
        }
        bool yes = true;
        for(vector<int> i:query){
            for(int j='a';j<='z';j++){
                if(pref[i[1]][j]-pref[i[0]-1][j]>=2){
                    yes = false;
                }
            }
        }
        if(yes){
            high = mid;
        }
        else{
            low = mid+1;
        }
    }
    cout << low << "\n";
    return 0;
}

Compilation message (stderr)

grudanje.cpp: In function 'int main()':
grudanje.cpp:36:31: warning: array subscript has type 'char' [-Wchar-subscripts]
   36 |                 pref[i][s[i-1]]++;
      |                               ^

• 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