제출 #416283

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
416283		Theo830	말 (IOI15_horses)	C++17	0 / 100	880 ms	57940 KiB

horses

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<ll> distr;
ll rnd(ll a, ll b){return distr(rng)%(b-a+1)+a;}
#include "horses.h"
/*
int init(int N, int X[], int Y[]);
int updateX(int pos, int val);
int updateY(int pos, int val);



int main() {
	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];
	}

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

	int M;
    cin>>M;
	for (int i = 0; i < M; i++) {
		int type;
		cin>>type;
		int pos;
		int val;
		cin>>pos>>val;
		if (type == 1) {
			printf("%d\n",updateX(pos,val));
		} else if (type == 2) {
			printf("%d\n",updateY(pos,val));
		}
	}

	return 0;
}
*/
ll seg[2000005]={0},se[200005]={0};
ll y[500000];
ll n;
void build(ll s,ll e,ll idx){
    if(s == e){
        seg[idx] = y[s-1];
        return;
    }
    ll mid = (s+e)/2;
    build(s,mid,idx*2);
    build(mid+1,e,idx*2+1);
    seg[idx] = max(seg[idx*2],seg[idx*2+1]);
}
void update(ll s,ll e,ll qs,ll qe,ll idx,ll k){
    if(s == e && s == qs){
        seg[idx] = k;
        return;
    }
    if(qs > e || qe < s){
        return;
    }
    ll mid = (s+e)/2;
    update(s,mid,qs,qe,idx*2,k);
    update(mid+1,e,qs,qe,idx*2+1,k);
    seg[idx] = max(seg[idx*2],seg[idx*2+1]);
}
ll query(ll s,ll e,ll qs,ll qe,ll idx){
    if(qs <= s && e <= qe){
        return seg[idx];
    }
    if(qs > e || qe < s){
        return 0;
    }
    ll mid = (s+e)/2;
    ll a = query(s,mid,qs,qe,idx*2);
    ll b = query(mid+1,e,qs,qe,idx*2+1);
    return max(a,b);
}
ll x[500000];
void build2(ll s,ll e,ll idx){
    if(s == e){
        se[idx] = x[s-1];
        return;
    }
    ll mid = (s+e)/2;
    build2(s,mid,idx*2);
    build2(mid+1,e,idx*2+1);
    se[idx] = (se[idx*2] * se[idx*2+1]) % INF;
}
void update2(ll s,ll e,ll qs,ll qe,ll idx,ll k){
    if(s == e && s == qs){
        se[idx] = k;
        return;
    }
    if(qs > e || qe < s){
        return;
    }
    ll mid = (s+e)/2;
    update2(s,mid,qs,qe,idx*2,k);
    update2(mid+1,e,qs,qe,idx*2+1,k);
    se[idx] = (se[idx*2] * se[idx*2+1]) % INF;
}
ll query2(ll s,ll e,ll qs,ll qe,ll idx){
    if(qs <= s && e <= qe){
        return se[idx];
    }
    if(qs > e || qe < s){
        return 1;
    }
    ll mid = (s+e)/2;
    ll a = query2(s,mid,qs,qe,idx*2);
    ll b = query2(mid+1,e,qs,qe,idx*2+1);
    return (a * b) % INF;
}
set<ii>ar;
ll power(ll a,ll b){
    if(b == 0){
        return 1;
    }
    if(b == 1){
        return a;
    }
    ll ans = power(a,b/2);
    ans *= ans;
    ans %= INF;
    if(b % 2){
        ans *= a;
    }
    return ans % INF;
}
ll inv(ll a){
    return power(a,INF-2);
}
int solve(void){
    ll num = 1;
    ll p = 0;
    ll product = query2(1,n,1,n,1);
    ll num2 = 1,y2 = y[n-1];
    auto it = ar.begin();
    ll last = n;
    while(num <= 1e9 && p != ar.size()){
        ll y1 = query(1,n,-(*it).F+2,last,1);
        if(y1 * num2 > y2 * num){
            y2 = y1;
            num2 = num;
        }
        last = -(*it).F+1;
        num *= (*it).S;
        it++;
        p++;
    }
    if(num <= 1e9){
        ll y1 = query(1,n,1,last,1);
        if(y1 * num2 > y2 * num){
            y2 = y1;
            num2 = num;
        }
    }
    ll ans = (((product * inv(num2)) % INF) * y2) % INF;
    return ans;
}
int init(int N, int X[], int Y[]) {
    n = N;
    f(i,0,N){
        y[i] = Y[i];
        x[i] = X[i];
    }
    build(1,N,1);
    build2(1,N,1);
    ll ans = 0;
    ll pos = N - 1;
    while(pos >= 0){
        if(x[pos] > 1 || pos == 0){
            ar.insert(ii(-pos,x[pos]));
        }
        pos--;
    }
	return solve();
}

int updateX(int pos, int val){
    if(ar.count(ii(-pos,x[pos]))){
        ar.erase(ii(-pos,x[pos]));
    }
    x[pos] = val;
    update2(1,n,pos+1,pos+1,1,val);
    if(val != 1 || pos == 0){
        ar.insert(ii(-pos,x[pos]));
    }
	return solve();
}

int updateY(int pos, int val){
    y[pos] = val;
    update(1,n,pos+1,pos+1,1,val);
	return solve();
}
/*
3
2 1 3
3 4 1
1
2 1 2
*/

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

horses.cpp: In function 'int solve()':
horses.cpp:170:11: warning: conversion from 'll' {aka 'long long int'} to 'double' may change value [-Wconversion]
  170 |     while(num <= 1e9 && p != ar.size()){
      |           ^~~
horses.cpp:170:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::set<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |     while(num <= 1e9 && p != ar.size()){
      |                         ~~^~~~~~~~~~~~
horses.cpp:181:8: warning: conversion from 'll' {aka 'long long int'} to 'double' may change value [-Wconversion]
  181 |     if(num <= 1e9){
      |        ^~~
horses.cpp:189:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  189 |     return ans;
      |            ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:199:8: warning: unused variable 'ans' [-Wunused-variable]
  199 |     ll ans = 0;
      |        ^~~

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