Submission #871659

#TimeUsernameProblemLanguageResultExecution timeMemory
871659vjudge1Difference (POI11_roz)C++17
60 / 100
1103 ms11716 KiB
#include "bits/stdc++.h" #define ii pair <int, int> #define F first #define S second using namespace std; const int N = 1e6+5; int n; char a[N]; int sum[N]; int pre[N]; vector <int> save[30]; int Get(int i, int j) { return sum[j] - sum[i-1]; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin >> n; for (int i = 1 ; i <= n ; i++) { cin >> a[i]; save[a[i]-'a'].push_back(i); } int res = 0; for (int c1 = 0 ; c1 < 26 ; c1++) for (int c2 = 0 ; c2 < 26 ; c2++) { if (c1 == c2) continue; vector <ii> pos; pos.push_back(ii(0, 0)); for (int i : save[c1]) pos.push_back(ii(i, 1)); for (int i : save[c2]) pos.push_back(ii(i, -1)); sort(pos.begin(), pos.end()); int cur = 0; for (int i = 1 ; i < pos.size() ; i++) { int l = 1, r = i, ans = 0; cur += pos[i].S; sum[i] = sum[i-1] + (pos[i].S == -1) ; while(l <= r) { int mid = (l + r) / 2; if (Get(mid, i)) { ans = mid; l = mid + 1; } else r = mid - 1; } if (ans) res = max(res, cur-pre[ans-1]); pre[i] = min(cur, pre[i-1]); } } cout << res; return 0; }

Compilation message (stderr)

roz.cpp: In function 'int main()':
roz.cpp:33:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |             for (int i = 1 ; i < pos.size() ; i++) {
      |                              ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...