Submission #921612

#	Time	Username	Problem	Language	Result	Execution time	Memory
921612		ByeWorld	Horses (IOI15_horses)	C++14	34 / 100	65 ms	40220 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
const int MAXN = 2e5+10;
const int MOD = 1e9+7;
const int INF = 1e9;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;

ll mul(ll x, ll y){
	ll num = (x*y)%MOD;
	return num;
}

int n;
ll x[MAXN], y[MAXN], mx, idx;
set <int> S;

struct seg {
	ll st[4*MAXN]; 
	void bd(int id, int l, int r){
		if(l==r){
            st[id] = x[l];
            return;
        }
		bd(lf, l, md); bd(rg, md+1, r);
        st[id] = mul(st[lf], st[rg]);
	}
	ll que(int id, int l, int r, int x, int y){
		if(x<=l && r<=y) return st[id];
		if(r<x || y<l) return 1;
		return mul(que(lf, l, md, x, y), que(rg, md+1, r, x, y));
	}
	ll upd(int id, int l, int r, int x, ll p){
		if(l==r && x==l){
			return st[id] = p;
		}
		if(r<x || x<l) return st[id];
		return st[id] = mul(upd(lf, l, md, x, p), 
            upd(rg, md+1, r, x, p));
	}
} A;
struct segtree {
	ll st[4*MAXN]; // pr[i] * y[i]
	void bd(int id, int l, int r){
		if(l==r){
            st[id] = y[l]; return;
        }
		bd(lf, l, md); bd(rg, md+1, r);
        st[id] = max(st[lf], st[rg]);
	}
	ll que(int id, int l, int r, int x, int y){
		if(x<=l && r<=y) return st[id];
		if(r<x || y<l) return -INF;
		return max(que(lf, l, md, x, y), que(rg, md+1, r, x, y));
	}
	ll upd(int id, int l, int r, int x, ll p){
		if(l==r && l==x){
			return st[id] = p;
		}
		if(r<x || x<l) return st[id];
		return st[id] = max(upd(lf, l, md, x, p), 
            upd(rg, md+1, r, x, p));
	}
} B;

vector <pii> cand;
int calc(){
    cand.clear();
	auto it = S.end();
    int L = -1, R = n; 
    ll mY = -1;
    for (int i=0;i<30;i++) {
        --it;
        L = *it;
        mY = B.que(1, 1, n, L, R);
        cand.pb(pii(mY, L));
        R = L-1;
        if (R == 0) { // udh keluar
            break;
        }
    }
    
    ll opt = 0, prod=1;
    for (int i=0;i<cand.size();i++) {
        if (cand[opt].fi*prod < cand[i].fi) {
            opt = i;
            prod = 1;
        }
        prod *= x[cand[i].se];
        if (prod > INF) {
            break;
        }
    }
    ll ans = mul(A.que(1, 1, n, 1, cand[opt].se), 
        cand[opt].fi);
    return (int)(ans);
}

int init(int N, int X[], int Y[]) {
	n = N;
    S.insert(1);
	for(int i=1; i<=n; i++) {
		x[i] = X[i-1]; y[i] = Y[i-1];
        if(x[i] != 1) S.insert(i);
	}
    A.bd(1, 1, n);
    B.bd(1, 1, n);
    
	return calc();
}

int updateX(int pos, int val) {	
    pos++;
    if(x[pos] != 1 && val == 1) S.erase(pos); 
    if(x[pos] == 1 && val != 1) S.insert(pos);
    S.insert(1);
    
	x[pos] = val; 
    // upd segtree X
    A.upd(1, 1, n, pos, val);
    
	return calc();
}

int updateY(int pos, int val) {
    pos++;
	y[pos] = val; 
    // upd segtree Y
    B.upd(1, 1, n, pos, val);
    
	return calc();
}

Compilation message (stderr)

horses.cpp: In member function 'long long int seg::que(int, int, int, int, int)':
horses.cpp:37:42: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   37 |  ll que(int id, int l, int r, int x, int y){
      |                                      ~~~~^
horses.cpp:24:13: note: shadowed declaration is here
   24 | ll x[MAXN], y[MAXN], mx, idx;
      |             ^
horses.cpp:37:35: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   37 |  ll que(int id, int l, int r, int x, int y){
      |                               ~~~~^
horses.cpp:24:4: note: shadowed declaration is here
   24 | ll x[MAXN], y[MAXN], mx, idx;
      |    ^
horses.cpp: In member function 'long long int seg::upd(int, int, int, int, long long int)':
horses.cpp:42:35: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   42 |  ll upd(int id, int l, int r, int x, ll p){
      |                               ~~~~^
horses.cpp:24:4: note: shadowed declaration is here
   24 | ll x[MAXN], y[MAXN], mx, idx;
      |    ^
horses.cpp: In member function 'long long int segtree::que(int, int, int, int, int)':
horses.cpp:60:42: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   60 |  ll que(int id, int l, int r, int x, int y){
      |                                      ~~~~^
horses.cpp:24:13: note: shadowed declaration is here
   24 | ll x[MAXN], y[MAXN], mx, idx;
      |             ^
horses.cpp:60:35: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   60 |  ll que(int id, int l, int r, int x, int y){
      |                               ~~~~^
horses.cpp:24:4: note: shadowed declaration is here
   24 | ll x[MAXN], y[MAXN], mx, idx;
      |    ^
horses.cpp: In member function 'long long int segtree::upd(int, int, int, int, long long int)':
horses.cpp:65:35: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   65 |  ll upd(int id, int l, int r, int x, ll p){
      |                               ~~~~^
horses.cpp:24:4: note: shadowed declaration is here
   24 | ll x[MAXN], y[MAXN], mx, idx;
      |    ^
horses.cpp: In function 'int calc()':
horses.cpp:93:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for (int i=0;i<cand.size();i++) {
      |                  ~^~~~~~~~~~~~

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