Submission #60107

#	Time	Username	Problem	Language	Result	Execution time	Memory
60107		istlemin	Horses (IOI15_horses)	C++14	34 / 100	1553 ms	124312 KiB

horses

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

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

ll n;
vi x;
vi y;

ll mod = 1e9+7;

class OldNode{
public:
    ll val = 1;
    ll dn,up;
    OldNode *left;
    OldNode *right;

    OldNode(ll _dn,ll _up){
		dn = _dn;
		up = _up;
        if(dn+1!=up){
            left = new OldNode(dn,(dn+up)/2);
            right = new OldNode((dn+up)/2,up);
        }
    }

    ll update(ll a,ll v){
        if(dn>a||up<=a) return val;
        if(dn+1==up) {
			return val = v;
        }
        return val = (left->update(a,v)*right->update(a,v))%mod;
    }

    ll query(ll a,ll b){
        if(dn>=b||up<=a) return 1;
        if(a<=dn&&up<=b) return val;
        return (left->query(a,b)*right->query(a,b))%mod;
    }
};

pair<double,ll> op1(pair<double,ll> a,double b){
    return {a.first+b,a.second};
}

class Node{
public:
    pair<double,ll> val = {0,0};
    double toPush = 0;
    ll dn,up;
    Node *left;
    Node *right;

    Node(ll _dn,ll _up){
		dn = _dn;
		up = _up;
		val.second = up-1;
        if(dn+1!=up){
            left = new Node(dn,(dn+up)/2);
            right = new Node((dn+up)/2,up);
        }
    }

    void push(){
        if(dn+1==up) return;
        left->val=op1(left->val,toPush);
        right->val=op1(right->val,toPush);
        left->toPush+=toPush;
        right->toPush+=toPush;
        toPush = 0;
    }

    pair<double,ll> update(ll a,ll b,double v){
        if(dn>=b||up<=a) return val;
        if(a<=dn&&up<=b) {
            val=op1(val,v);
            toPush+=v;
			return val;
        }
        push();
        return val = max(left->update(a,b,v),right->update(a,b,v));
    }

    pair<double,ll> query(ll a,ll b){
        if(dn>=b||up<=a) return {-1e18,0};
        if(a<=dn&&up<=b) return val;
        push();
        return max(left->query(a,b),right->query(a,b));
    }
};

Node *st;
OldNode *stMul;

ll getAns(){
    ll index = st->query(0,n).second;
    ll ans = (stMul->query(0,index+1)*y[index])%mod;
    return ans;
}

int init(int N, int X[], int Y[]) {
	n = N;
    x.resize(n,1);
    y.resize(n,1);
	st = new Node(0,N);
	stMul = new OldNode(0,N);
    rep(i,0,n){
        updateX(i,X[i]);
        updateY(i,Y[i]);
	}
    /*srand(4564);
	ll n = 100;
    Node st(0,n);
    vector<double> v(n,0);
    rep(i,0,100){
        if(rand()%2){
            ll a = rand()%n;
            ll b = rand()%n;
            if(b<a) continue;
            ll mul = rand()%10+1;
            st.update(a,b,mul);
            rep(j,a,b) v[j]+=mul;
        } else {
            ll a = rand()%n;
            ll b = rand()%n;
            if(b<a) continue;
            double mx = -1e18;
            ll mxIndex = 0;
            rep(j,a,b) {
				if(v[j]>=mx){
					mx = v[j];
					mxIndex = j;
				}
            }

            //if(mx==-1e18&&mx==-1e18) continue;
            pair<double,ll> res = st.query(a,b);
            cout<<mx<<" "<<mxIndex<<" "<<" "<<res.first<<" "<<res.second<<endl;

        }
    }
/*
    ll n = 10;
    Node st(0,n);

	st.update(2,7,3);
	st.update(1,8,4);
	st.update(5,9,5);
	st.update(3,4,10);
	pair<double,ll> res = st.query(0,3);
	cout<<res.first<<" "<<res.second<<endl;
*/
    //rep(i,0,10) cout<<st.query(i,i+1)<<" ";
    //cout<<endl;
	/*cout<<"init "<<N<<endl;
	rep(i,0,N) cout<<X[i]<<" ";
	cout<<endl;
	rep(i,0,N) cout<<Y[i]<<" ";
	cout<<endl;*/
	return getAns();
}

int updateX(int pos, int val) {
	//cout<<"updateX "<<pos<<" "<<val<<endl;
	//cout<<pos<<" "<<n<<" "<<-log(double(x[pos]))<<endl;
	//cout<<st<<end;
    st->update(pos,n,-log(double(x[pos]))+log(double(val)));
    stMul->update(pos,val);
    x[pos] = val;
	return getAns();
}

int updateY(int pos, int val) {
	//cout<<"updateY "<<pos<<" "<<val<<endl;
    st->update(pos,pos+1,-log(y[pos])+log(val));
    y[pos] = val;
	return getAns();
}

Compilation message (stderr)

horses.cpp:152:1: warning: "/*" within comment [-Wcomment]
 /*
  
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:170:15: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return getAns();
         ~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:180:15: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return getAns();
         ~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:187:15: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return getAns();
         ~~~~~~^~

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