제출 #1133997

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1133997		ackhava	말 (IOI15_horses)	C++20	37 / 100	556 ms	52292 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define REP(v, i, j) for (int v = i; v != j; v++)
#define FORI(v) for (auto i : v)
#define FORJ(v) for (auto j : v)

#define OUT(v, a) \
    FORI(v)       \
    cout << i << a;
#define OUTS(v, a, b)      \
    cout << v.size() << a; \
    OUT(v, b)
#define in(a, n) \
    REP(i, 0, n) \
    cin >> a[i];

#define SORT(v) sort(begin(v), end(v))
#define REV(v) reverse(begin(v), end(v))
#define MEMSET(m) memset(m, -1, sizeof m)

#define pb push_back
#define fi first
#define se second

#define detachIO                      \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0);
    
using namespace std;

template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
bool operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
    if(__x.size() != __y.size()) return false;
    return std::equal(__x.begin(), __x.end(), __y.begin());
}


typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<pii, pii> piiii;

const int MOD = 1e9+7;

struct modint {
    long long val;

    modint() = default;
    modint(int _val): val(_val){}
    modint operator+(modint b){ return ((this->val + b.val)%MOD); }
    modint operator-(modint b){ return ((MOD + this->val - b.val)%MOD); }
    modint operator*(modint b){ return ((this->val * b.val)%MOD); }
    modint operator^(int a){
        if(a==0)return 1;
        if(a==1)return *this;
        return (((*this)*(*this))^(a>>1))*((*this)^(a&1)); 
    }
};

modint invert(modint a){
    return a^(MOD-2);
}

modint operator/(modint a, modint b){
    return a*invert(b);
}

struct segment_tree_1 {
    long long n;
    typedef int T;
    vector<T> seg;
    const T e = 0;

    T merge(T a, T b){
        if(a==e)return b;
        if(b==e)return a;
        return max(a,b);
    }

    segment_tree_1(long long _n): n(_n),seg(4*_n+10,e) /** BUG: GCC does not initialize the elements properly this way */ {
        for(auto &i:seg)i=e;
    }

    void update(long long pos, long long l, long long r, long long idx, T val){
        if(r<idx)return;
        if(l>idx)return;
        if(l==r){
            // Merge logic...
            seg[pos]=val;
            return;
        }
        update(pos*2+1,l,(l+r)/2,idx,val);
        update(pos*2+2,((l+r)/2)+1,r,idx,val);
        seg[pos]=merge(seg[pos*2+1],seg[pos*2+2]);
    }

    T query(long long pos, long long l, long long r, long long ql, long long qr){
        if(l > qr)return e;
        if(ql > r)return e;
        if(ql <= l && r <= qr)return seg[pos];
        if(l==r)return e;
        return merge(query(pos*2+1,l,(l+r)/2,ql,qr),query(pos*2+2,((l+r)/2)+1,r,ql,qr));
    }
};

struct segment_tree_2 {
    long long n;
    typedef long long T;
    vector<T> seg;
    const T e = 1;

    T merge(T a, T b){
        if(a==e)return b;
        if(b==e)return a;
        return (a*b)%MOD;
    }

    segment_tree_2(long long _n): n(_n),seg(4*_n+10,e) /** BUG: GCC does not initialize the elements properly this way */ {
        for(auto &i:seg)i=e;
    }

    void update(long long pos, long long l, long long r, long long idx, T val){
        if(r<idx)return;
        if(l>idx)return;
        if(l==r){
            seg[pos]=val%MOD;
            return;
        }
        update(pos*2+1,l,(l+r)/2,idx,val);
        update(pos*2+2,((l+r)/2)+1,r,idx,val);
        seg[pos]=merge(seg[pos*2+1],seg[pos*2+2]);
    }

    T query(long long pos, long long l, long long r, long long ql, long long qr){
        if(l > qr)return e;
        if(ql > r)return e;
        if(ql <= l && r <= qr)return seg[pos];
        if(l==r)return e;
        return merge(query(pos*2+1,l,(l+r)/2,ql,qr),query(pos*2+2,((l+r)/2)+1,r,ql,qr));
    }
};

int N;

set<int> s1, s2;

segment_tree_1 y(0);
segment_tree_2 x(0);

int init(int N, int X[], int Y[]) {
	::N = N;

	long long ans=0;
	bool run_mod=false;

	REP(i,0,N){
		auto ix=N-i-1;
		if(!run_mod)ans=max<long long>(ans,Y[ix]);
		ans*=X[ix];
		if(ans>=(1e9+7))ans%=(long long)(1e9+7),run_mod=true;
	}

    y.n=N+20;
    y.seg.resize(4*y.n+10);
    for(auto &i:y.seg)i=y.e;
    x.n=N+20;
    x.seg.resize(4*x.n+10);
    for(auto &i:x.seg)i=x.e;
    
    REP(i,0,N){
        x.update(0,0,N,i,X[i]);
        y.update(0,0,N,i,Y[i]);
    }

    REP(i,0,N){
        if(X[i]>1)s2.insert(i);
    }

    while(s1.size() < 30 && s2.size()){
        s1.insert(*s2.rbegin());
        s2.erase(*s2.rbegin());
    }
    while(s1.size() && s2.size() && *s2.rbegin() > *s1.begin()){
        int a=*s2.rbegin();
        int b=*s1.begin();
        s1.insert(a);
        s2.insert(b);
        s1.erase(b);
        s2.erase(a);
    }

	return ans;
}

int updateX(int pos, int val) {	
    x.update(0,0,N,pos,val);

    if(val == 1)s1.erase(pos),s2.erase(pos);
    else {
        if(!s1.count(pos) && !s2.count(pos))s2.insert(pos);
    }

    while(s1.size() < 30 && s2.size()){
        s1.insert(*s2.rbegin());
        s2.erase(*s2.rbegin());
    }
    while(*s2.rbegin() > *s1.begin()){
        int a=*s2.rbegin();
        int b=*s1.begin();
        s1.insert(a);
        s2.insert(b);
        s1.erase(b);
        s2.erase(a);
    }

	long long ans=0;
	bool run_mod=false;

    auto it = s1.rbegin();
    for(;it!=s1.rend();it++){
        if(!run_mod){
            ans=max<long long>(ans,y.query(0,0,N,*it,N));
        }
        ans*=x.query(0,0,N,*it,*it);
        if(ans>MOD)run_mod=true,ans%=MOD;
    }

    if(s2.size()){
        ans *= x.query(0,0,N,0,*s2.rbegin());
        ans%=MOD;
    }

	return ans;
}

int updateY(int pos, int val) {
    y.update(0,0,N,pos,val);

	long long ans=0;
	bool run_mod=false;
    
    auto it = s1.rbegin();
    for(;it!=s1.rend();it++){
        if(!run_mod){
            ans=max<long long>(ans,y.query(0,0,N,*it,N));
        }
        ans*=x.query(0,0,N,*it,*it);
        if(ans>MOD)run_mod=true,ans%=MOD;
    }

    if(s2.size()){
        ans *= x.query(0,0,N,0,*s2.rbegin());
        ans%=MOD;
    }

	return ans;
}

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