제출 #707603

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
707603		baojiaopisu	말 (IOI15_horses)	C++14	34 / 100	23 ms	12228 KiB

horses

#include<bits/stdc++.h>
#include "horses.h"
 
using namespace std;
 
using ll = long long;
using ld = long double;
using ull = unsigned long long;
 
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
 
#define fi first
#define se second
#define left BAO
#define right ANH
#define pb push_back
#define pf push_front
#define mp make_pair
#define ins insert
#define btpc __builtin_popcount
#define btclz __builtin_clz
 
#define sz(x) (int)(x.size());
#define all(x) x.begin(), x.end()
#define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
 
template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (x > y)
        {
            x = y;
            return true;
        }
        return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y)
        {
            x = y;
            return true;
        }
        return false;
    }
 
const int MOD = 1e9 + 7; //998244353
 
template<class X, class Y>
	void add(X &x, const Y &y) {
		x = (x + y);
		if(x >= MOD) x -= MOD;
	}
 
template<class X, class Y> 
	void sub(X &x, const Y &y) {
		x = (x - y);
		if(x < 0) x += MOD;
	}
 
/* Author : Le Ngoc Bao Anh, 12A5, LQD High School for Gifted Student*/
 
const ll INF = 1e9;
const int N = 1e5 + 10;
 
template <typename T> T mod_inv_in_range(T a, T m) {
    // assert(0 <= a && a < m);
    T x = a, y = m;
    T vx = 1, vy = 0;
    while (x) {
        T k = y / x;
        y %= x;
        vy -= k * vx;
        std::swap(x, y);
        std::swap(vx, vy);
    }
    assert(y == 1);
    return vy < 0 ? m + vy : vy;
}
 
template <typename T> T mod_inv(T a, T m) {
    a %= m;
    a = a < 0 ? a + m : a;
    return mod_inv_in_range(a, m);
}
 
template <int MOD_> struct modnum {
    static constexpr int MOD = MOD_;
    static_assert(MOD_ > 0, "MOD must be positive");
 
    using ll = long long;
 
    int v;
 
public:
 
    modnum() : v(0) {}
    modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
    explicit operator int() const { return v; }
    friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
    friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }
 
    friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
    friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
 
    modnum inv() const {
        modnum res;
        res.v = mod_inv_in_range(v, MOD);
        return res;
    }
    friend modnum inv(const modnum& m) { return m.inv(); }
    modnum neg() const {
        modnum res;
        res.v = v ? MOD-v : 0;
        return res;
    }
    friend modnum neg(const modnum& m) { return m.neg(); }
 
    modnum operator- () const {
        return neg();
    }
    modnum operator+ () const {
        return modnum(*this);
    }
 
    modnum& operator ++ () {
        v ++;
        if (v == MOD) v = 0;
        return *this;
    }
    modnum& operator -- () {
        if (v == 0) v = MOD;
        v --;
        return *this;
    }
    modnum& operator += (const modnum& o) {
        v -= MOD-o.v;
        v = (v < 0) ? v + MOD : v;
        return *this;
    }
    modnum& operator -= (const modnum& o) {
        v -= o.v;
        v = (v < 0) ? v + MOD : v;
        return *this;
    }
    modnum& operator *= (const modnum& o) {
        v = int(ll(v) * ll(o.v) % MOD);
        return *this;
    }
    modnum& operator /= (const modnum& o) {
        return *this *= o.inv();
    }
 
    friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
    friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
    friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
    friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
    friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
    friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
};
using num = modnum<MOD>;
 
template <class T> struct FenwickTree {
	int n;
	vector<T> bit;
 
	FenwickTree(int _n = 0) {
		n = _n;
		bit.resize(n + 5);
		for(int i = 1; i <= n; i++) bit[i] = 1;
	}
 
	void update(int pos, T x) {
		for(int i = pos; i <= n; i += i & (-i)) bit[i] *= x;
	}
 
	T get(int pos) {
		T ans = 1;
		for(int i = pos; i > 0; i -= i & (-i)) ans *= bit[i];
		return ans;
	}
};
 
struct SegTree {
	int n;
	vector<int> node;
 
	SegTree(int _n = 0) {
		n = _n;
		node.resize(4 * n + 7);
	}
 
private:
	void Update(int l, int r, int pos, int val, int id) {
		if(l == r) {
			node[id] = val;
			return;
		}
 
		int mid = (l + r) >> 1;
		if(pos <= mid) Update(l, mid, pos, val, id << 1);
		else Update(mid + 1, r, pos, val, id << 1 | 1);
		node[id] = max(node[id << 1], node[id << 1 | 1]);
	}
 
	int Get(int l, int r, int lo, int hi, int id) {
		if(l > hi || r < lo) return 0;
		if(lo <= l && r <= hi) return node[id];
 
		int mid = (l + r) >> 1;
		int left = Get(l, mid, lo, hi, id << 1);
		int right = Get(mid + 1, r, lo, hi, id << 1 | 1);
		return max(left, right);	
	}
 
public:
	void update(int pos, int val) {
		Update(1, n, pos, val, 1);
	}
 
	int get(int l, int r) {
		return Get(1, n, l, r, 1);
	}
};
SegTree IT = SegTree(10);
FenwickTree<num> BIT;
set<int> curr;
int x[N], y[N], n;
 
int calc() {
	int pos = n;
	auto iter = curr.end(); iter = prev(iter);
	ll r = 0;
	int ans = 0;
	while(true) {
		int t = (*iter);
 
		int v = IT.get(t, pos);
		if(v > r) {
			r = v;
			int cc = BIT.get(t).v;
			ans = 1ll * cc * v % MOD;
		}
		pos = t - 1;
 
		r = r * x[(*iter)];
		if(r > INF) break;
		if(iter == curr.begin()) break;
		iter = prev(iter);
	}
 
	return ans;
}
 
int init(int N, int X[], int Y[]) {
	n = N;
	for(int i = n; i >= 1; i--) {
		x[i] = X[i - 1];
		y[i] = Y[i - 1];
	}
 
	IT = SegTree(n); BIT = FenwickTree<num>(n);
 
	curr.ins(1);
	for(int i = 1; i <= n; i++) {
		IT.update(i, y[i]);
		BIT.update(i, x[i]);
		if(x[i] > 1) curr.ins(i);
	}
 
	return calc();
}
 
int updateX(int pos, int val) {
	pos++;
	if(x[pos] > 1) curr.erase(pos);
	BIT.update(pos, num(1) / num(x[pos]));
	x[pos] = val;
	if(x[pos] > 1) curr.ins(pos);
	if(x[1] == 1) curr.ins(1);
	BIT.update(pos, x[pos]);
	return calc();
}
 
int updateY(int pos, int val) {
	++pos;
	y[pos] = val;
	IT.update(pos, y[pos]);
	return calc();
}

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

horses.cpp: In function 'int calc()':
horses.cpp:249:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  249 |    ans = 1ll * cc * v % MOD;
      |          ~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:262:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
  262 | int init(int N, int X[], int Y[]) {
      |          ~~~~^
horses.cpp:71:11: note: shadowed declaration is here
   71 | const int N = 1e5 + 10;
      |           ^

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