oj.uz

Submission #60104

# Submission time Handle Problem Language Result Execution time Memory
60104 2018-07-23T16:26:57 Z istlemin Horses (IOI15_horses) C++14
34 / 100
 1500 ms 155752 KB 
#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(){
	/*cout<<"#######"<<endl;
	rep(i,0,n) cout<<x[i]<<" ";
	cout<<endl;
	rep(i,0,n) cout<<y[i]<<" ";
	cout<<endl;
	rep(i,0,n) cout<<stMul->query(i,i+1)<<" ";
	cout<<endl;
	rep(i,0,n) cout<<st->query(i,i+1).first<<" ";
	cout<<endl;
	cout<<"#######"<<endl;*/

    ll index = st->query(0,n).second;
    ll ans = (stMul->query(0,index+1)*y[index])%mod;
    //cout<<ans<<endl;
	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])));
    st->update(pos,n,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]));
    st->update(pos,pos+1,log(val));
    y[pos] = val;
	return getAns();
}

Compilation message

horses.cpp:164:1: warning: "/*" within comment [-Wcomment]
 /*
  
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:182: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:193: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:201:15: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return getAns();
         ~~~~~~^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Correct 3 ms 492 KB Output is correct
6 Correct 3 ms 584 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 4 ms 640 KB Output is correct
12 Correct 3 ms 640 KB Output is correct
13 Correct 3 ms 640 KB Output is correct
14 Correct 3 ms 640 KB Output is correct
15 Correct 3 ms 640 KB Output is correct
16 Correct 2 ms 640 KB Output is correct
17 Correct 3 ms 640 KB Output is correct
18 Correct 3 ms 640 KB Output is correct
19 Correct 3 ms 640 KB Output is correct
20 Correct 2 ms 640 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 3 ms 640 KB Output is correct
12 Correct 3 ms 640 KB Output is correct
13 Correct 4 ms 640 KB Output is correct
14 Correct 3 ms 640 KB Output is correct
15 Correct 2 ms 640 KB Output is correct
16 Correct 3 ms 640 KB Output is correct
17 Correct 3 ms 640 KB Output is correct
18 Correct 3 ms 640 KB Output is correct
19 Correct 3 ms 640 KB Output is correct
20 Correct 2 ms 640 KB Output is correct
21 Correct 3 ms 640 KB Output is correct
22 Correct 3 ms 640 KB Output is correct
23 Correct 6 ms 892 KB Output is correct
24 Correct 6 ms 928 KB Output is correct
25 Correct 6 ms 996 KB Output is correct
26 Correct 7 ms 1028 KB Output is correct
27 Correct 6 ms 1108 KB Output is correct
28 Correct 8 ms 1264 KB Output is correct
29 Correct 5 ms 1264 KB Output is correct
30 Correct 7 ms 1264 KB Output is correct
31 Correct 5 ms 1264 KB Output is correct
32 Correct 5 ms 1264 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1222 ms 124856 KB Output is correct
2 Execution timed out 1591 ms 136896 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 136896 KB Output is correct
2 Correct 2 ms 136896 KB Output is correct
3 Correct 3 ms 136896 KB Output is correct
4 Correct 3 ms 136896 KB Output is correct
5 Correct 3 ms 136896 KB Output is correct
6 Correct 3 ms 136896 KB Output is correct
7 Correct 3 ms 136896 KB Output is correct
8 Correct 3 ms 136896 KB Output is correct
9 Correct 2 ms 136896 KB Output is correct
10 Correct 3 ms 136896 KB Output is correct
11 Correct 2 ms 136896 KB Output is correct
12 Correct 2 ms 136896 KB Output is correct
13 Correct 2 ms 136896 KB Output is correct
14 Correct 3 ms 136896 KB Output is correct
15 Correct 2 ms 136896 KB Output is correct
16 Correct 2 ms 136896 KB Output is correct
17 Correct 4 ms 136896 KB Output is correct
18 Correct 2 ms 136896 KB Output is correct
19 Correct 3 ms 136896 KB Output is correct
20 Correct 4 ms 136896 KB Output is correct
21 Correct 3 ms 136896 KB Output is correct
22 Correct 3 ms 136896 KB Output is correct
23 Correct 5 ms 136896 KB Output is correct
24 Correct 6 ms 136896 KB Output is correct
25 Correct 5 ms 136896 KB Output is correct
26 Correct 6 ms 136896 KB Output is correct
27 Correct 4 ms 136896 KB Output is correct
28 Correct 7 ms 136896 KB Output is correct
29 Correct 5 ms 136896 KB Output is correct
30 Correct 6 ms 136896 KB Output is correct
31 Correct 5 ms 136896 KB Output is correct
32 Correct 5 ms 136896 KB Output is correct
33 Execution timed out 1567 ms 140300 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 140300 KB Output is correct
2 Correct 3 ms 140300 KB Output is correct
3 Correct 3 ms 140300 KB Output is correct
4 Correct 3 ms 140300 KB Output is correct
5 Correct 3 ms 140300 KB Output is correct
6 Correct 3 ms 140300 KB Output is correct
7 Correct 3 ms 140300 KB Output is correct
8 Correct 2 ms 140300 KB Output is correct
9 Correct 3 ms 140300 KB Output is correct
10 Correct 2 ms 140300 KB Output is correct
11 Correct 3 ms 140300 KB Output is correct
12 Correct 3 ms 140300 KB Output is correct
13 Correct 2 ms 140300 KB Output is correct
14 Correct 4 ms 140300 KB Output is correct
15 Correct 2 ms 140300 KB Output is correct
16 Correct 3 ms 140300 KB Output is correct
17 Correct 2 ms 140300 KB Output is correct
18 Correct 0 ms 140300 KB Output is correct
19 Correct 2 ms 140300 KB Output is correct
20 Correct 3 ms 140300 KB Output is correct
21 Correct 3 ms 140300 KB Output is correct
22 Correct 2 ms 140300 KB Output is correct
23 Correct 8 ms 140300 KB Output is correct
24 Correct 8 ms 140300 KB Output is correct
25 Correct 6 ms 140300 KB Output is correct
26 Correct 5 ms 140300 KB Output is correct
27 Correct 5 ms 140300 KB Output is correct
28 Correct 9 ms 140300 KB Output is correct
29 Correct 7 ms 140300 KB Output is correct
30 Correct 6 ms 140300 KB Output is correct
31 Correct 5 ms 140300 KB Output is correct
32 Correct 6 ms 140300 KB Output is correct
33 Correct 1378 ms 145304 KB Output is correct
34 Execution timed out 1566 ms 155752 KB Time limit exceeded
35 Halted 0 ms 0 KB -