Submission #500960

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
500960	2022-01-01T18:18:24 Z	Mounir	Difference (POI11_roz)	C++14	10 / 100	1000 ms	16528 KB

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
#define pb push_back
#define pii pair<int, int>
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
#define x first
#define y second
#define int long long
using namespace std;

signed main(){
      int nVals; cin >> nVals;
      string line; cin >> line;

      vector<int> posis[26];
      for (int i = 0; i < nVals; ++i)
            posis[line[i] - 'a'].pb(i);
      
      int maxi = 0;
      int pt = 0;
      for (int i = 0; i < nVals;){
            pt = i;
            while (pt < nVals && line[pt] == line[i])
                  ++pt;
            chmax(maxi, pt - i);
            i = pt;
      }

      for (int iMin = 0; iMin < 26; ++iMin)
            for (int iMax = 0; iMax < 6; ++iMax){
                  if (posis[iMin].empty() || posis[iMax].empty()) continue;
                  vector<pii> vals;
                  for (int posi : posis[iMin])
                        vals.pb({posi, -1});
                  for (int posi : posis[iMax])
                        vals.pb({posi, 1});
                  sort(all(vals));
                  int nCur = sz(vals) + 1;

                  vector<int> p(nCur), pMin(nCur), pMax(nCur);
                  int dern1 = 0, dern0 = 0;
                  int id = 1, pCur = 0;
                  p[0] = pMin[0] = pMax[0];
                  for (pii val : vals){
                        pCur += val.second;
                        p[id] = pCur;
                        pMax[id] = max(pMax[id - 1], p[id]);
                        pMin[id] = min(pMin[id - 1], p[id]);
                        if (val.second == 1) {
                              dern1 = id;
                              if (dern0 != 0){
                                    chmax(maxi, abs(pMax[dern0 - 1] - p[id]));
                                  ///  cout << dern0 << " " << pMax[dern0 - 1] << " " << p[id] << endl;
                                    chmax(maxi, abs(pMin[dern0 - 1] - p[id]));
                              }
                        }
                        else {
                              dern0 = id;
                              if (dern1 != 0){
                                    chmax(maxi, abs(pMax[dern1 - 1] - p[id]));
                                    chmax(maxi, abs(pMin[dern1 - 1] - p[id]));
                              }
                        }
                        id++;
                  }
            }
      cout << maxi << endl;
      return 0;   
}

Subtask #1
0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	204 KB	Output is correct
2	Correct	204 KB	Output is correct
3	Correct	204 KB	Output is correct
4	Incorrect	252 KB	Output isn't correct

Subtask #2
10.0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	204 KB	Output is correct
2	Correct	204 KB	Output is correct
3	Correct	204 KB	Output is correct

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	204 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	332 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	6 ms	460 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	89 ms	1780 KB	Output is correct
2	Incorrect	0 ms	204 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #7
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1097 ms	16528 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1098 ms	16464 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1097 ms	16008 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1097 ms	16468 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Submission #500960

Compilation message