제출 #365029

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
365029		BartolM	말 (IOI15_horses)	C++17	57 / 100	1593 ms	71324 KiB

horses

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

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
const int OFF=(1<<19);
const int MAXN=5e5+5;

int n;
pll T[2*OFF];
ll Tmax[2*OFF];
ll x[MAXN], y[MAXN];
set <int> S;

ll mul(ll a, ll b) {
    return a*b%MOD;
}

pll f(pll a, pll b) {
    return mp(mul(a.X, b.X), min((ll)MOD, a.Y*b.Y));
}

pll umn(int a, int b, int pos=1, int lo=0, int hi=OFF) {
    if (lo>=a && hi<=b) return T[pos];
    if (lo>=b || hi<=a) return mp(1, 1);
    int mid=(lo+hi)/2;
    return f(umn(a, b, pos*2, lo, mid), umn(a, b, pos*2+1, mid, hi));
}

ll maxi(int a, int b, int pos=1, int lo=0, int hi=OFF) {
    if (lo>=a && hi<=b) return Tmax[pos];
    if (lo>=b || hi<=a) return 1;
    int mid=(lo+hi)/2;
    return max(maxi(a, b, pos*2, lo, mid), maxi(a, b, pos*2+1, mid, hi));
}

int mrg(int a, int b, ll ya, ll yb) {
    if (a==n) return b;
    if (b==n) return a;
    ll bb=f(umn(a+1, b+1), mp(yb, yb)).Y;
    return bb>=ya ? b : a;
}

ll answer() {
    if (S.size()==1) return maxi(0, n);

    int res=n, cnt=31; ll yres=0;
    set <int>::iterator it=S.end(); it--;
    while (it!=S.begin() && cnt) {
        auto nx=it;
        it--;
        cnt--;
        ll curr_y=maxi(*it, *nx);

        res=mrg(*it, res, curr_y, yres);
        if (res==*it) yres=curr_y;
    }
    return mul(umn(0, res+1).X, yres);
}

int init(int N, int XX[], int YY[]) {
    n=N;
    for (int i=0; i<n; ++i) x[i]=XX[i], y[i]=YY[i];
    for (int i=0; i<n; ++i) if (x[i]!=1) S.insert(i);
    S.insert(n); S.insert(0);

    memset(Tmax, 0, sizeof Tmax);
    fill(T, T+2*OFF, mp(1, 1));
    for (int i=0; i<n; ++i) Tmax[OFF+i]=y[i], T[OFF+i].X=T[OFF+i].Y=x[i];
    for (int i=OFF-1; i>0; --i) T[i]=f(T[i*2], T[i*2+1]), Tmax[i]=max(Tmax[i*2], Tmax[i*2+1]);

    return answer();
}

int updateY(int pos, int val) {
    y[pos]=val;
    pos+=OFF;
    Tmax[pos]=val;
    pos/=2;
    while (pos) {
        Tmax[pos]=max(Tmax[pos*2], Tmax[pos*2+1]);
        pos/=2;
    }
    return answer();
}

int updateX(int pos, int val) {

    if (val!=1) S.insert(pos);
    x[pos]=val;
    if (val==1 && S.count(pos)) S.erase(pos);
    S.insert(0);

    pos+=OFF;
    T[pos].X=T[pos].Y=val;
    pos/=2;

    while (pos) {
        T[pos]=f(T[pos*2], T[pos*2+1]);
        pos/=2;
    }
    return answer();
}

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

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:84:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   84 |     return answer();
      |            ~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:96:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   96 |     return answer();
      |            ~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:114:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  114 |     return answer();
      |            ~~~~~~^~

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