Submission #733267

#	Time	Username	Problem	Language	Result	Execution time	Memory
733267		That_Salamander	Horses (IOI15_horses)	C++17	100 / 100	1194 ms	68696 KiB

horses

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <cstring>
#include <queue>
#include <unordered_set>
#include <unordered_map>

#define FOR(var,bound) for(int var = 0; var < bound; var++)
#define FORB(var,lb,ub) for (int var = lb; var < ub; var++)
#define FORR(var,bound) for(int var = bound-1; var >= 0; var--)
#define MAX 1000000007ll

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

int n;
vector<int> x, y;

vector<ll> t(2000000, 1);
vector<int> tMax(2000000, 0);
set<int> nonOneX;

void update(int n, int tl, int tr, int idx, ll val) {
    if (tl == tr) {
        t[n] = val;

        if (val == 1) {
            nonOneX.erase(idx);
        } else {
            nonOneX.insert(idx);
        }

        return;
    }

    int m = (tl + tr) / 2;
    if (idx <= m) update(n * 2, tl, m, idx, val);
    else update(n*2+1, m + 1, tr, idx, val);

    t[n]  = (t[n*2] * t[n*2+1]) % MAX;
}

ll query(int n, int tl, int tr, int ql, int qr) {
    if (qr < tl || tr < ql) {
        return 1;
    } else if (ql <= tl && tr <= qr) {
        return t[n];
    } else {
        int m = (tl + tr) / 2;
        return (
            query(n*2  , tl, m, ql, qr) *
            query(n*2+1, m+1, tr, ql, qr)
        ) % MAX;
    }
}

void updateY(int n, int tl, int tr, int idx, int val) {
    if (tl == tr) {
        tMax[n] = val;

        return;
    }

    int m = (tl + tr) / 2;
    if (idx <= m) updateY(n * 2, tl, m, idx, val);
    else updateY(n*2+1, m + 1, tr, idx, val);

    tMax[n]  = max(tMax[n*2], tMax[n*2+1]);
}

int queryY(int n, int tl, int tr, int ql, int qr) {
    if (qr < tl || tr < ql) {
        return 1;
    } else if (ql <= tl && tr <= qr) {
        return tMax[n];
    } else {
        int m = (tl + tr) / 2;
        return max(
            queryY(n*2  , tl, m, ql, qr),
            queryY(n*2+1, m+1, tr, ql, qr)
        );
    }
}

int solve() {
    ll best = 0;

    ll horses = 1;
    ll mul = 1;
    ll mulToBeat = 0;

    if (nonOneX.size() == 0) {
        return queryY(1, 0, n-1, 0, n-1);
    }


    auto it = nonOneX.begin();

    if (*it != 0) {
        best = mulToBeat = queryY(1, 0, n - 1, 0, *it - 1);
    }

    if (nonOneX.size() > 35) {
        it = nonOneX.end();

        for (int i = 0; i < 33; i++) {
            it--;
        }

        horses = query(1, 0, n - 1, 0, (*it) - 1);
    }

    while (it != nonOneX.end()) {
        int xVal = x[*it];
        int yVal;
        auto nit = it; nit++;
        if (nit == nonOneX.end()) {
            yVal = queryY(1, 0, n - 1, *it, n - 1);
        } else {
            yVal = queryY(1, 0, n - 1, *it, *nit - 1);
        }

        horses = (horses * xVal) % MAX;
        ll price = (horses * yVal) % MAX;

        mul *= xVal;

        if (mul >= mulToBeat || mul * yVal >= mulToBeat) {
            mulToBeat = yVal;
            best = price;
            mul = 1;
        }

        it++;
    }

    return best % MAX;
}

int init(int N, int X[], int Y[]) {
    n = N;
    x.resize(N); y.resize(N);

    FOR(i, N) {
        x[i] = X[i];
        y[i] = Y[i];
        update(1, 0, n - 1, i, X[i]);
        updateY(1, 0, n - 1, i, Y[i]);
    }

    return solve();
}

int updateX(int pos, int val) {
    x[pos] = val;
    update(1, 0, n-1, pos, val);
    return solve();
}

int updateY(int pos, int val) {
    y[pos] = val;
    updateY(1, 0, n - 1, pos, val);
    return solve();
}


#ifdef LOCAL_TEST
static char buffer[1024];
static int currentChar = 0;
static int charsNumber = 0;

static inline int readInt() {
  int x;
  cin >> x;
  return x;
}

int main() {
  int N;
  N = readInt();

  int *X = (int *)malloc(sizeof(int) * (unsigned int)N);
  int *Y = (int *)malloc(sizeof(int) * (unsigned int)N);

  for (int i = 0; i < N; i++) {
    X[i] = readInt();
  }

  for (int i = 0; i < N; i++) {
    Y[i] = readInt();
  }

  printf("%d\n", init(N, X, Y));

  int M;
  M = readInt();

  for (int i = 0; i < M; i++) {
    int type;
    type = readInt();
    int pos;
    pos = readInt();
    int val;
    val = readInt();

    if (type == 1) {
      printf("%d\n", updateX(pos, val));
    } else if (type == 2) {
      printf("%d\n", updateY(pos, val));
    }
  }

  return 0;
}

#endif

Compilation message (stderr)

horses.cpp: In function 'void update(int, int, int, int, ll)':
horses.cpp:32:17: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   32 | void update(int n, int tl, int tr, int idx, ll val) {
      |             ~~~~^
horses.cpp:25:5: note: shadowed declaration is here
   25 | int n;
      |     ^
horses.cpp: In function 'll query(int, int, int, int, int)':
horses.cpp:52:14: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   52 | ll query(int n, int tl, int tr, int ql, int qr) {
      |          ~~~~^
horses.cpp:25:5: note: shadowed declaration is here
   25 | int n;
      |     ^
horses.cpp: In function 'void updateY(int, int, int, int, int)':
horses.cpp:66:18: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   66 | void updateY(int n, int tl, int tr, int idx, int val) {
      |              ~~~~^
horses.cpp:25:5: note: shadowed declaration is here
   25 | int n;
      |     ^
horses.cpp: In function 'int queryY(int, int, int, int, int)':
horses.cpp:80:16: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   80 | int queryY(int n, int tl, int tr, int ql, int qr) {
      |            ~~~~^
horses.cpp:25:5: note: shadowed declaration is here
   25 | int n;
      |     ^
horses.cpp: In function 'int solve()':
horses.cpp:146:17: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  146 |     return best % MAX;
      |                 ^

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 23 / 23