Submission #432939

#	Time	Username	Problem	Language	Result	Execution time	Memory
432939		wiwiho	Horses (IOI15_horses)	C++14	17 / 100	1557 ms	43256 KiB

horses

#include "horses.h"

#include <bits/stdc++.h>

#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;

struct SegmentTree{
    vector<int> st;
    void modify(int pos, int v, int L, int R, int id){
        if(L == R){
            st[id] = v;
            return;
        }
        int M = (L + R) / 2;
        if(pos <= M) modify(pos, v, L, M, 2 * id + 1);
        else modify(pos, v, M + 1, R, 2 * id + 2);
        st[id] = max(st[2 * id + 1], st[2 * id + 2]);
    }
    int query(int l, int r, int L, int R, int id){
        if(l == L && r == R){
            return st[id];
        }
        int M = (L + R) / 2;
        if(r <= M) return query(l, r, L, M, 2 * id + 1);
        else if(l > M) return query(l, r, M + 1, R, 2 * id + 2);
        else return max(query(l, M, L, M, 2 * id + 1), query(M + 1, r, M + 1, R, 2 * id + 2));
    }
};

struct BIT{
    vector<ll> bit;
    int lowbit(int x){
        return x & -x;
    }
    void modify(int x, ll v){
        x++;
        for(; x < bit.size(); x += lowbit(x)){
            bit[x] = bit[x] * v % MOD;
        }
    }
    ll query(int x){
        x++;
        ll ans = 1;
        for(; x > 0; x -= lowbit(x)){
            ans = ans * bit[x] % MOD;
        }
        return ans;
    }
};

ll inv(ll a){
    ll b = MOD - 2;
    ll ans = 1;
    while(b > 0){
        if(b & 1) ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

SegmentTree st;
BIT bit;
int n;
vector<int> x, y;
set<int> large;

ll calc(){
    //cerr << "test\n";
    //printv(large, cerr);
    int now = n;
    ll ans = 0;
    int cnt = 0;
    while(ans <= 10 && now >= 0){
        //cerr << now << " " << ans << "\n";
        ans = ans * x[now];
        auto it = large.lower_bound(now);
        int nxt;
        if(it == large.begin()) nxt = 0;
        else nxt = *prev(it) + 1;
        //cerr << nxt << "\n";
        ans = max(ans, (ll)st.query(nxt, now, 0, n, 0));
        now = nxt - 1;
    }
    ans %= MOD;
    //printv(x, cerr);
    //printv(bit.bit, cerr);
    if(now >= 0) ans = ans * bit.query(now) % MOD;
    //cerr << "ok " << now << " " << ans << "\n";
    return ans;
}

void qq(){
    st.st.clear();
    bit.bit.clear();
    large.clear();
    st.st.resize(4 * (n + 1));
    bit.bit.resize(n + 1, 1);
    x[n] = 1;
    for(int i = 0; i < n; i++){
        st.modify(i + 1, y[i + 1], 0, n, 0);
        bit.modify(i, x[i]);
        if(x[i] >= 2) large.insert(i);
    }
}

int init(int N, int X[], int Y[]){
    n = N;
    x.resize(n + 1);
    y.resize(n + 1);
    for(int i = 0; i < n; i++){
        x[i] = X[i];
        y[i + 1] = Y[i];
    }
    qq();
    ll ans = calc();
    //printv(x, cerr);
    //printv(y, cerr);
	return ans;
}

int updateX(int pos, int val){	
    /*if(x[pos] >= 2) large.erase(pos);
    bit.modify(pos, inv(x[pos]) * val % MOD);
    x[pos] = val;
    if(val >= 2) large.insert(pos);*/
    x[pos] = val;
    qq();
	return calc();
}

int updateY(int pos, int val){
    /*pos++;
    y[pos] = val;
    st.modify(pos, val, 0, n, 0);*/
    pos++;
    y[pos] = val;
    qq();
	return calc();
}

Compilation message (stderr)

horses.cpp: In member function 'void BIT::modify(int, ll)':
horses.cpp:46:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(; x < bit.size(); x += lowbit(x)){
      |               ~~^~~~~~~~~~~~
horses.cpp: In function 'll calc()':
horses.cpp:82:9: warning: unused variable 'cnt' [-Wunused-variable]
   82 |     int cnt = 0;
      |         ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:128:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  128 |  return ans;
      |         ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:138:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  138 |  return calc();
      |         ~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:148:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  148 |  return calc();
      |         ~~~~^~

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