제출 #590873

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
590873		AlperenT	말 (IOI15_horses)	C++17	100 / 100	846 ms	104984 KiB

horses

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

using namespace std;

const int N = 5e5 + 5, MOD = 1e9 + 7;

struct mint{
    int val;

    mint(long long a = 0) : val(a % MOD) {if(val < 0) val += MOD; }
    mint(long long a, long long b) {*this += a, *this /= b; }

    mint &operator += (const mint &b) {val += b.val; if(val >= MOD) val -= MOD; return *this; }
    mint &operator -= (const mint &b) {val -= b.val; if(val < 0) val += MOD; return *this; }
    mint &operator *= (const mint &b) {val = (1ll * val * b.val) % MOD; return *this; }
    mint &operator /= (const mint &b) {*this *= minv(b); return *this; }

    mint &operator ++ () {return *this += 1; }
    mint operator ++ (int) {mint tmp = *this; *this += 1; return tmp; }

    mint &operator -- () {return *this -= 1; }
    mint operator -- (int) {mint tmp = *this; *this -= 1; return tmp; }

    friend mint operator + (mint a, const mint &b) {return a += b; }
    friend mint operator - (mint a, const mint &b) {return a -= b; }
    friend mint operator - (const mint &a) {return 0 - a; }
    friend mint operator * (mint a, const mint &b) {return a *= b; }
    friend mint operator / (mint a, const mint &b) {return a /= b; }

    friend istream &operator >> (istream &is, mint &a) {long long b; cin >> b; a = b; return is; }
    friend ostream &operator << (ostream &os, const mint &a) {cout << a.val; return os; }

    mint mexp(mint a, long long b){
        mint c = 1;
        for(; b > 0; b /= 2, a *= a) if(b & 1) c *= a;
        return c;
    }

    mint minv(const mint &a) {return mexp(a, MOD - 2); }
};

int n, x[N], y[N];

struct SegTree{
	pair<long double, int> tree[N * 4];
	long double lazy[N * 4];

	void push(int v){
		if(lazy[v]){
			tree[v].first += lazy[v];

			if(v * 2 < N * 4) lazy[v * 2] += lazy[v], lazy[v * 2 + 1] += lazy[v];

			lazy[v] = 0;
		}
	}

	pair<long double, int> merge(pair<long double, int> a, pair<long double, int> b){
		return max(a, b);
	}

	void build(int v = 1, int l = 0, int r = n - 1){
		if(l == r) tree[v] = {0, l};
		else{
			int m = l + (r - l) / 2;

			build(v * 2, l, m);
			build(v * 2 + 1, m + 1, r);

			tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
		}
	}

	void update(int l, int r, long double val, int v = 1, int tl = 0, int tr = n - 1){
		if(l > r) return;
		else if(tl == l && tr == r) lazy[v] += val;
		else{
			push(v);

			int tm = tl + (tr - tl) / 2;

			update(l, min(r, tm), val, v * 2, tl, tm);
			update(max(l, tm + 1), r, val, v * 2 + 1, tm + 1, tr);

			push(v * 2), push(v * 2 + 1);

			tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
		}
	}

	int query(){
		push(1);
		return tree[1].second;
	}
};

SegTree sgt;

struct Fenwick{
	mint tree[N];

	Fenwick(){
		fill(tree, tree + N, mint(1));
	}

	mint query(int r){
		mint ans = 1;
		for(int i = r + 1; i > 0; i -= i & -i) ans *= tree[i];
		return ans;
	}

	void update(int pos, mint val){
		for(int i = pos + 1; i < N; i += i & -i) tree[i] *= val;
	}
};

Fenwick fw;

int init(int N_, int X[], int Y[]){
	n = N_;

	copy(X, X + n, x);
	copy(Y, Y + n, y);

	sgt.build();

	for(int i = 0; i < n; i++){
		sgt.update(i, n - 1, log(x[i]));
		sgt.update(i, i, log(y[i]));

		fw.update(i, x[i]);
	}

	int ans = sgt.query();

	return (fw.query(ans) * y[ans]).val;
}

int updateX(int pos, int val){	
	sgt.update(pos, n - 1, log(val) - log(x[pos]));
	fw.update(pos, mint(val) / x[pos]);

	x[pos] = val;

	int ans = sgt.query();

	return (fw.query(ans) * y[ans]).val;
}

int updateY(int pos, int val){
	sgt.update(pos, pos, log(val) - log(y[pos]));
	y[pos] = val;

	int ans = sgt.query();

	return (fw.query(ans) * y[ans]).val;;
}

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

horses.cpp: In constructor 'mint::mint(long long int)':
horses.cpp:11:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   11 |     mint(long long a = 0) : val(a % MOD) {if(val < 0) val += MOD; }
      |                                 ~~^~~~~
horses.cpp: In member function 'mint& mint::operator*=(const mint&)':
horses.cpp:16:66: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   16 |     mint &operator *= (const mint &b) {val = (1ll * val * b.val) % MOD; return *this; }
      |                                              ~~~~~~~~~~~~~~~~~~~~^~~~~

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