Submission #871655

#TimeUsernameProblemLanguageResultExecution timeMemory
871655vjudge1Difference (POI11_roz)C++17
10 / 100
528 ms65536 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][30]; int pre[N]; vector <int> save[30]; int Get(int i, int j, int k) { return sum[j][k] - sum[i-1][k]; } 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); for (int j = 0 ; j < 26 ; j++) sum[i][j] = sum[i-1][j] + (a[i]-'a' == j); } 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 = pos[i].F, ans = 0; while(l <= r) { int mid = (l + r) / 2; if (Get(mid, pos[i].F, c2)) { ans = mid; l = mid + 1; } else r = mid - 1; } cur += pos[i].S; 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:35: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]
   35 |             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...