Hacker Cups and Balls

// lol
 
 
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
 
using namespace std;
#define F first
#define S second
 
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  int t[n], sc[n+1];
  map<int, int> srange;
  for (int i = 0; i < n; ++i) {
    cin >> t[i];
    srange[i] = 0;
  }
  int lop = 0;
  pair<int, int> op[m];
  int opt[m];
  for (int i = 0; i < m; ++i) {
    cin >> op[i].F >> op[i].S;
    op[i].F--, op[i].S--;
    if (op[i].F > op[i].S) {
      opt[i] = 1;
      swap(op[i].F, op[i].S);
    } else opt[i] = 0;
    if (op[i].F <= n/2 && op[i].S >= n/2) lop = i+1;
  }
  for (int i = 0; i < lop; ++i) {
    auto it = --srange.upper_bound(op[i].S);
    pair<int, int> asd = *it;
    if (asd.F <= op[i].F) {
      if (asd.S == opt[i]) continue;
      else {
        reverse(t+op[i].F, t+op[i].S+1);
        srange[op[i].S+1] = asd.S;
        srange[op[i].F] = opt[i];
      }
    } else {
      srange.erase(srange.lower_bound(op[i].F), srange.upper_bound(op[i].S));
      srange[op[i].F] = opt[i];
      srange[op[i].S+1] = asd.S;
      if (op[i].S-op[i].F <= 1000) {
        sort(t+op[i].F, t+op[i].S+1);
      } else {
        for (int j = 1; j <= n; ++j) sc[j] = 0;
        for (int j = op[i].F; j <= op[i].S; ++j) {
          sc[t[j]]++;
        }
        int j = op[i].F;
        for (int k = 1; k <= n; ++k) if (sc[j]) t[j++] = k;
      }
      if (opt[i]) reverse(t+op[i].F, t+op[i].S+1);
    }
    // for (int i = 0; i < n; ++i) cout << t[i] << " ";
    // cout << endl;
  }
  cout << t[n/2] << endl;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: WRONG ANSWER

Test 14

Verdict: WRONG ANSWER

Test 15

Verdict: TIME LIMIT EXCEEDED

Test 16

Verdict: TIME LIMIT EXCEEDED

Test 17

Verdict: TIME LIMIT EXCEEDED

Test 18

Verdict: TIME LIMIT EXCEEDED

Test 19

Verdict: TIME LIMIT EXCEEDED

Test 20

Verdict: TIME LIMIT EXCEEDED

Test 21

Verdict: TIME LIMIT EXCEEDED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: TIME LIMIT EXCEEDED

Test 24

Verdict: TIME LIMIT EXCEEDED

Test 25

Verdict: WRONG ANSWER

Test 26

Verdict: WRONG ANSWER