Submission #559495

#	Time	Username	Problem	Language	Result	Execution time	Memory
559495		joshjms	Horses (IOI15_horses)	C++14	100 / 100	836 ms	65544 KiB

horses

#include "horses.h"

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define debug(x) cout << #x << " => " << x << "\n";

const long long mod = 1e9 + 7;

ll n, x[500005], y[500005];

struct node {
    ll idx, val, nxt, prv;
} arr[500005];

set <ll> st;

ll tree[2000005];

void upd(ll idx, ll l, ll r, ll x, ll v) {
    if(l == r) {
        tree[idx] = v;
        return;
    }
    ll mid = (l + r) / 2;
    if(x <= mid) upd(idx * 2, l, mid, x, v);
    else upd(idx * 2 + 1, mid + 1, r, x, v);
    tree[idx] = (tree[idx * 2] * tree[idx * 2 + 1]) % mod;
}

ll query(ll idx, ll l, ll r, ll x, ll y) {
    if(l > r || l > y || r < x) return 1;
    if(l >= x && r <= y) return tree[idx];
    ll mid = (l + r) / 2;
    return (query(idx * 2, l, mid, x, y) * query(idx * 2 + 1, mid + 1, r, x, y)) % mod;
}

ll maxy[2000005];

void updy(ll idx, ll l, ll r, ll x, ll v) {
    if(l == r) {
        maxy[idx] = v;
        return;
    }
    ll mid = (l + r) / 2;
    if(x <= mid) updy(idx * 2, l, mid, x, v);
    else updy(idx * 2 + 1, mid + 1, r, x, v);
    maxy[idx] = max(maxy[idx * 2], maxy[idx * 2 + 1]);
}

ll queryy(ll idx, ll l, ll r, ll x, ll y) {
    if(l > r || l > y || r < x) return 0;
    if(l >= x && r <= y) return maxy[idx];
    ll mid = (l + r) / 2;
    return max(queryy(idx * 2, l, mid, x, y), queryy(idx * 2 + 1, mid + 1, r, x, y));
}

int init(int N, int X[], int Y[]) {
	n = N;
    for(ll i = 1; i <= n; i++) {
        x[i] = X[i - 1];
        y[i] = Y[i - 1];
        upd(1, 1, n, i, x[i]);
        updy(1, 1, n, i, y[i]);
    }
    for(ll i = 1; i <= n; i++) {
        if(x[i] > 1) {
            st.insert(i);
        }
    }
    x[n + 1] = 1;
    st.insert(n + 1);
    x[0] = 1;
    st.insert(0);
    auto it = st.end();
    pair <ll,ll> maxi = {0, 0};
    vector <ll> tmp;
    for(ll mul = 1; it != st.begin();) {
        it--;
        mul *= x[*it];
        tmp.pb(*it);
        if(mul > 1e9) break;
    }
    reverse(tmp.begin(), tmp.end());
    for(ll i = 0, mul = 1; i < tmp.size() - 1; i++) {
        ll max_y = queryy(1, 1, n, tmp[i], tmp[i + 1] - 1);
        maxi = max(maxi, {mul * max_y, tmp[i]});
        mul *= x[tmp[i + 1]];
    }
    auto nuit = st.upper_bound(maxi.se);
    return (query(1, 1, n, 1, maxi.se) * queryy(1, 1, n, maxi.se, *nuit - 1)) % mod; 
}

int updateX(int pos, int val) {	
    pos++;
	x[pos] = val;
    if(x[pos] == 1) st.erase(pos);
    else st.insert(pos);
    upd(1, 1, n, pos, val);
    auto it = st.end();
    pair <ll,ll> maxi = {0, 0};
    vector <ll> tmp;
    for(ll mul = 1; it != st.begin();) {
        it--;
        mul *= x[*it];
        tmp.pb(*it);
        if(mul > 1e9) break;
    }
    reverse(tmp.begin(), tmp.end());
    for(ll i = 0, mul = 1; i < tmp.size() - 1; i++) {
        ll max_y = queryy(1, 1, n, tmp[i], tmp[i + 1] - 1);
        maxi = max(maxi, {mul * max_y, tmp[i]});
        mul *= x[tmp[i + 1]];
    }
    auto nuit = st.upper_bound(maxi.se);
    return (query(1, 1, n, 1, maxi.se) * queryy(1, 1, n, maxi.se, *nuit - 1)) % mod; 
}

int updateY(int pos, int val) {
    pos++;
    y[pos] = val;
	updy(1, 1, n, pos, val);
    auto it = st.end();
    pair <ll,ll> maxi = {0, 0};
    vector <ll> tmp;
    for(ll mul = 1; it != st.begin();) {
        it--;
        mul *= x[*it];
        tmp.pb(*it);
        if(mul > 1e9) break;
    }
    reverse(tmp.begin(), tmp.end());
    for(ll i = 0, mul = 1; i < tmp.size() - 1; i++) {
        ll max_y = queryy(1, 1, n, tmp[i], tmp[i + 1] - 1);
        maxi = max(maxi, {mul * max_y, tmp[i]});
        mul *= x[tmp[i + 1]];
    }
    auto nuit = st.upper_bound(maxi.se);
    return (query(1, 1, n, 1, maxi.se) * queryy(1, 1, n, maxi.se, *nuit - 1)) % mod; 
}

// static char _buffer[1024];
// static int _currentChar = 0;
// static int _charsNumber = 0;
// static FILE *_inputFile, *_outputFile;

// static inline int _read() {
//     if (_charsNumber < 0) {
//         exit(1);
//     }
//     if (!_charsNumber || _currentChar == _charsNumber) {
//         _charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
//         _currentChar = 0;
//     }
//     if (_charsNumber <= 0) {
//         return -1;
//     }
//     return _buffer[_currentChar++];
// }

// static inline int _readInt() {
//     int c, x, s;
//     c = _read();
//     while (c <= 32) c = _read();
//     x = 0;
//     s = 1;
//     if (c == '-') {
//         s = -1;
//         c = _read();
//     }
//     while (c > 32) {
//         x *= 10;
//         x += c - '0';
//         c = _read();
//     }
//     if (s < 0) x = -x;
//     return x;
// }


// int main() {
// 	// _inputFile = fopen("horses.in", "rb");
// 	// _outputFile = fopen("horses.out", "w");
	
// 	int N; cin >> N;

// 	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++) {
// 		cin >> X[i];
// 	}

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

// 	// fprintf(_outputFile,"%d\n",init(N,X,Y));

//     cout << init(N, X, Y) << "\n";

// 	int M; cin >> M;

// 	for (int i = 0; i < M; i++) {
// 		int type; cin >> type;
// 		int pos; cin >> pos;
// 		int val; cin >> val;

// 		if (type == 1) {
//             cout << updateX(pos, val) << "\n";
// 		} else if (type == 2) {
//             cout << updateY(pos, val) << "\n";
// 		}
// 	}

// 	return 0;
// }


// int main() {
// 	// _inputFile = fopen("horses.in", "rb");
// 	// _outputFile = fopen("horses.out", "w");
	
// 	int N; cin >> N;

// 	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++) {
// 		cin >> X[i];
// 	}

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

// 	// fprintf(_outputFile,"%d\n",init(N,X,Y));

// 	int M; cin >> M;

// 	for (int i = 0; i < 7; i++) {
// 		int type; cin >> type;
// 		int pos; cin >> pos;
// 		int val; cin >> val;

// 		if (type == 1) {
//             X[pos] = val;
// 		} else if (type == 2) {
//             Y[pos] = val;
// 		}
// 	}

//     cout << init(N, X, Y) << "\n";

// 	return 0;
// }

Compilation message (stderr)

horses.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int)':
horses.cpp:25:33: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   25 | void upd(ll idx, ll l, ll r, ll x, ll v) {
      |                                 ^
horses.cpp:15:7: note: shadowed declaration is here
   15 | ll n, x[500005], y[500005];
      |       ^
horses.cpp: In function 'long long int query(long long int, long long int, long long int, long long int, long long int)':
horses.cpp:36:39: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   36 | ll query(ll idx, ll l, ll r, ll x, ll y) {
      |                                       ^
horses.cpp:15:18: note: shadowed declaration is here
   15 | ll n, x[500005], y[500005];
      |                  ^
horses.cpp:36:33: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   36 | ll query(ll idx, ll l, ll r, ll x, ll y) {
      |                                 ^
horses.cpp:15:7: note: shadowed declaration is here
   15 | ll n, x[500005], y[500005];
      |       ^
horses.cpp: In function 'void updy(long long int, long long int, long long int, long long int, long long int)':
horses.cpp:45:34: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   45 | void updy(ll idx, ll l, ll r, ll x, ll v) {
      |                                  ^
horses.cpp:15:7: note: shadowed declaration is here
   15 | ll n, x[500005], y[500005];
      |       ^
horses.cpp: In function 'long long int queryy(long long int, long long int, long long int, long long int, long long int)':
horses.cpp:56:40: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   56 | ll queryy(ll idx, ll l, ll r, ll x, ll y) {
      |                                        ^
horses.cpp:15:18: note: shadowed declaration is here
   15 | ll n, x[500005], y[500005];
      |                  ^
horses.cpp:56:34: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   56 | ll queryy(ll idx, ll l, ll r, ll x, ll y) {
      |                                  ^
horses.cpp:15:7: note: shadowed declaration is here
   15 | ll n, x[500005], y[500005];
      |       ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:87:12: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   87 |         if(mul > 1e9) break;
      |            ^~~
horses.cpp:90:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(ll i = 0, mul = 1; i < tmp.size() - 1; i++) {
      |                            ~~^~~~~~~~~~~~~~~~
horses.cpp:96:79: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   96 |     return (query(1, 1, n, 1, maxi.se) * queryy(1, 1, n, maxi.se, *nuit - 1)) % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:112:12: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
  112 |         if(mul > 1e9) break;
      |            ^~~
horses.cpp:115:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for(ll i = 0, mul = 1; i < tmp.size() - 1; i++) {
      |                            ~~^~~~~~~~~~~~~~~~
horses.cpp:121:79: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  121 |     return (query(1, 1, n, 1, maxi.se) * queryy(1, 1, n, maxi.se, *nuit - 1)) % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:135:12: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
  135 |         if(mul > 1e9) break;
      |            ^~~
horses.cpp:138:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |     for(ll i = 0, mul = 1; i < tmp.size() - 1; i++) {
      |                            ~~^~~~~~~~~~~~~~~~
horses.cpp:144:79: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  144 |     return (query(1, 1, n, 1, maxi.se) * queryy(1, 1, n, maxi.se, *nuit - 1)) % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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