oj.uz

Submission #970364

# Submission time Handle Problem Language Result Execution time Memory
970364 2024-04-26T12:21:03 Z anton Sequence (APIO23_sequence) C++17
28 / 100
 2000 ms 13468 KB 
#include "sequence.h"
#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>

struct MD{
  priority_queue<int> l, r;
  void balance(){
    while(r.size()>l.size()){
      int v= -r.top();
      r.pop();
      l.push(v);
    }
    while(l.size()>r.size()+1){
      int v= l.top();
      l.pop();
      r.push(-v);
    }
  }
  void insert(int v){
    if(l.size() == 0 || v<=l.top()){
      l.push(v);
    }
    else{
      r.push(-v);
    }

    balance();
  }

  vector<int> medians(){
    vector<int> res;
    if(l.size()>r.size()){
      res.push_back(l.top());
    }
    else{
      res.push_back(l.top());
      res.push_back(-r.top());
    }
    return res;
  }
};

int sequence(int N, std::vector<int> A) {
  int res= 0;
  for(int i = 0; i<N; i++){
    vector<int> oc(N, 0);
    MD md;
    for(int j = i; j<N; j++){
      //cout<<i<<" "<<j<<endl;
      oc[A[j]-1]++;
      md.insert(A[j]-1);
      //cout<<"sz "<<md.l.size()<<" "<<md.r.size()<<endl;
      for(auto e: md.medians()){
        res= max(res, oc[e]);
        //cout<<e<<" "<<oc[e]<<endl;
      }
    }
  }
  return res;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 161 ms 344 KB Output is correct
14 Correct 176 ms 460 KB Output is correct
15 Correct 168 ms 348 KB Output is correct
16 Correct 163 ms 596 KB Output is correct
17 Correct 155 ms 348 KB Output is correct
18 Correct 115 ms 456 KB Output is correct
19 Correct 159 ms 348 KB Output is correct
20 Correct 161 ms 464 KB Output is correct
21 Correct 161 ms 344 KB Output is correct
22 Correct 162 ms 344 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 2033 ms 12972 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Execution timed out 2079 ms 11144 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

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

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 161 ms 344 KB Output is correct
14 Correct 176 ms 460 KB Output is correct
15 Correct 168 ms 348 KB Output is correct
16 Correct 163 ms 596 KB Output is correct
17 Correct 155 ms 348 KB Output is correct
18 Correct 115 ms 456 KB Output is correct
19 Correct 159 ms 348 KB Output is correct
20 Correct 161 ms 464 KB Output is correct
21 Correct 161 ms 344 KB Output is correct
22 Correct 162 ms 344 KB Output is correct
23 Execution timed out 2061 ms 2720 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 161 ms 344 KB Output is correct
14 Correct 176 ms 460 KB Output is correct
15 Correct 168 ms 348 KB Output is correct
16 Correct 163 ms 596 KB Output is correct
17 Correct 155 ms 348 KB Output is correct
18 Correct 115 ms 456 KB Output is correct
19 Correct 159 ms 348 KB Output is correct
20 Correct 161 ms 464 KB Output is correct
21 Correct 161 ms 344 KB Output is correct
22 Correct 162 ms 344 KB Output is correct
23 Execution timed out 2033 ms 12972 KB Time limit exceeded
24 Halted 0 ms 0 KB -