제출 #288305

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
288305		shayan_p	Horses (IOI15_horses)	C++17	100 / 100	1035 ms	53436 KiB

horses

#include<bits/stdc++.h>
#include "horses.h"

#define F first
#define S second
#define PB push_back
#define sz(s) (int(s.size()))
#define bit(n, k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;

const int maxn = 5e5 + 10, mod = 1e9 + 7;

set<int> st; // reverse points
int n;
int val[4 * maxn], zr[4 * maxn];

void add(int pos, int x, int l = 0, int r = n, int id = 1){
    if(r-l == 1){
	val[id] = x;
	return;
    }
    int mid = (l+r) >> 1;
    if(pos < mid)
	add(pos, x, l, mid, 2*id);
    else
	add(pos, x, mid, r, 2*id+1);
    val[id] = max(val[2*id], val[2*id+1]);
}
int ask(int f, int s, int l = 0, int r = n, int id = 1){
    if(f >= s || l >= r || s <= l || r <= f)
	return 0;
    if(f <= l && r <= s)
	return val[id];
    int mid = (l+r) >> 1;
    return max(ask(f, s, l, mid, 2*id), ask(f, s, mid, r, 2*id+1));
}
void put(int pos, int x, int l = 0, int r = n, int id = 1){
    if(r-l == 1){
	zr[id] = x;
	return;
    }
    int mid = (l+r) >> 1;
    if(pos < mid)
	put(pos, x, l, mid, 2*id);
    else
	put(pos, x, mid, r, 2*id+1);
    zr[id] = 1ll * zr[2*id] * zr[2*id+1] % mod;
}
int zar(int pos, int l = 0, int r = n, int id = 1){
    if(pos <= l)
	return 1;
    if(r <= pos)
	return zr[id];
    int mid = (l + r) >> 1;
    return 1ll * zar(pos, l, mid, 2*id) * zar(pos, mid, r, 2*id+1) % mod;
}

int a[maxn], b[maxn];

int calc(){
    int bst = 0, lst = n;
    bool gr = 0;
    for(int x : st){
	x*=-1;
	bst = max(bst, ask(x, lst));
	lst = x;
	ll num = 1ll * a[x] * bst;
	bst = num % mod;
	if(num >= mod){
	    gr = 1;
	    break;
	}
    }
    if(!gr)
	return max(bst, ask(0, lst));
    else
	return 1ll * bst * zar(lst) % mod;
}
int init(int n, int X[], int Y[]){
    ::n = n;
    for(int i = 0; i < n; i++){
	a[i] = X[i], b[i] = Y[i];
	if(a[i] != 1)
	    st.insert(-i);
	put(i, a[i]), add(i, b[i]);
    }
    return calc();
}
int updateX(int pos, int val){
    if(val == 1)
	st.erase(-pos);
    else
	st.insert(-pos);
    a[pos] = val;
    put(pos, val);
    return calc();
}
int updateY(int pos, int val){
    b[pos] = val;
    add(pos, val);
    return calc();
}

컴파일 시 표준 에러 (stderr) 메시지

horses.cpp: In function 'void put(int, int, int, int, int)':
horses.cpp:52:42: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   52 |     zr[id] = 1ll * zr[2*id] * zr[2*id+1] % mod;
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int zar(int, int, int, int)':
horses.cpp:60:68: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   60 |     return 1ll * zar(pos, l, mid, 2*id) * zar(pos, mid, r, 2*id+1) % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int calc()':
horses.cpp:73:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   73 |  bst = num % mod;
      |        ~~~~^~~~~
horses.cpp:82:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   82 |  return 1ll * bst * zar(lst) % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:84:33: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   84 | int init(int n, int X[], int Y[]){
      |                                 ^
horses.cpp:19:5: note: shadowed declaration is here
   19 | int n;
      |     ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:94:29: warning: declaration of 'val' shadows a global declaration [-Wshadow]
   94 | int updateX(int pos, int val){
      |                             ^
horses.cpp:20:5: note: shadowed declaration is here
   20 | int val[4 * maxn], zr[4 * maxn];
      |     ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:103:29: warning: declaration of 'val' shadows a global declaration [-Wshadow]
  103 | int updateY(int pos, int val){
      |                             ^
horses.cpp:20:5: note: shadowed declaration is here
   20 | int val[4 * maxn], zr[4 * maxn];
      |     ^~~

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