Cod sursa(job #2462883)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 27 septembrie 2019 22:50:13
Problema Buline Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <iostream>
#include <cctype>
#include <cstdio>
#include <map>
#include <queue>

using namespace std;


const int SIZE = 1 << 17;
int pointer = SIZE;
char buffer[SIZE];

char Advance() {
  if (pointer == SIZE) {
    fread(buffer, 1, SIZE, stdin);
    pointer = 0;
  }
  return buffer[pointer++];
}

int Read() {
  int answer = 0;
  char ch = Advance();
  while (!isdigit(ch))
    ch = Advance();
  while (isdigit(ch)) {
    answer = answer * 10 + ch - '0';
    ch = Advance();
  }
  return answer;
}

typedef long long ll;
const int N = 200000 + 7;
int n;
ll sum[2 * N];

priority_queue <pair <ll, int>> pq;
map <pair <ll, int>, bool> del;

int main() {
  freopen ("buline.in", "r", stdin);
  freopen ("buline.out", "w", stdout);

  n = Read();
  for (int i = 1; i <= n; i++) {
    int x = Read(), y = Read();
    if (y == 0) {
      sum[i] = -x;
    } else {
      sum[i] = +x;
    }
    sum[i + n] = sum[i];
  }

  for (int i = 1; i <= 2 * n; i++) {
    sum[i] += sum[i - 1];
  }

  for (int i = 0; i < n; i++) {
    pq.push({sum[i], -i});
  }

  ll best = -(1LL << 60);
  int start, len;
  for (int i = 1; i <= n; i++) {
    pq.push({sum[i + n - 1], -(i + n - 1)});
    while (del[pq.top()]) {
      pq.pop();
    }
    pair <ll, int> it = pq.top();
    ll cur = it.first - sum[i - 1];
    if (cur > best) {
      best = cur;
      start = i;
      len = -it.second - i + 1;
    }
    del[ {sum[i - 1], -(i - 1)}] = 1;
  }

  cout << best << ' ' << start << ' ' << len << '\n';

  return 0;
}