Submission #153977

#	Time	Username	Problem	Language	Result	Execution time	Memory
153977		alexandra_udristoiu	Horses (IOI15_horses)	C++14	37 / 100	503 ms	55328 KiB

horses

#include<iostream>
#include<set>
#include "horses.h"
#define DIM 500005
#define mod 1000000007
#define f first
#define s second
using namespace std;
static int n;
static int x[DIM], y[DIM], lst[DIM], ym[DIM];
static pair<int, int> aint[4 * DIM], aux;
static set< pair<int, int> > w;
static void build(int nod, int st, int dr){
    if(st == dr){
        aint[nod] = make_pair(x[st], y[st]);
    }
    else{
        int mid = (st + dr) / 2;
        build(2 * nod, st, mid);
        build(2 * nod + 1, mid + 1, dr);
        aint[nod].f = aint[2 * nod].f * 1LL * aint[2 * nod + 1].f % mod;
        aint[nod].s = max(aint[2 * nod].s, aint[2 * nod + 1].s);
    }
}
static void update(int nod, int st, int dr, int p){
    if(st == dr){
        aint[nod] = make_pair(x[st], y[st]);
    }
    else{
        int mid = (st + dr) / 2;
        if(p <= mid){
            update(2 * nod, st, mid, p);
        }
        else{
            update(2 * nod + 1, mid + 1, dr, p);
        }
        aint[nod].f = aint[2 * nod].f * 1LL * aint[2 * nod + 1].f % mod;
        aint[nod].s = max(aint[2 * nod].s, aint[2 * nod + 1].s);
    }
}
static void query(int nod, int st, int dr, int p, int u){
    if(p <= st && dr <= u){
        if(aux.f != 0){
            aux.f = aux.f * 1LL * aint[nod].f % mod;
        }
        aux.s = max(aux.s, aint[nod].s);
    }
    else{
        int mid = (st + dr) / 2;
        if(p <= mid){
            query(2 * nod, st, mid, p, u);
        }
        if(u > mid){
            query(2 * nod + 1, mid + 1, dr, p, u);
        }
    }
}
static int solve(){
    int i, ind, ymax;
    long long val, sol;
    set< pair<int, int> > :: iterator it;
    val = 1;
    it = w.end();
    it--;
    for(; it != w.begin(); it--){
        val *= x[ it->f ];
        if(val > 1000000000){
            break;
        }
    }
    val = 1;
    sol = ymax = y[ it->f ];
    ind = it->f;
    it++;
    for(; it != w.end(); it++){
        val *= x[ it->f ];
        if(sol < val * ym[it->f]){
            sol = val * ym[it->f];
            ymax = ym[it->f];
            ind = it->s;
        }
    }
    aux = make_pair(1, 0);
    query(1, 1, n, 1, ind);
    return aux.f * 1LL * ymax % mod;
}
int init(int N, int X[], int Y[]) {
	n = N;
	w.insert( make_pair(0, 0) );
	int lst;
	for(int i = 1; i <= n; i++){
        x[i] = X[i - 1];
        y[i] = Y[i - 1];
	}
	build(1, 1, n);
	for(int i = 1; i <= n; i++){
        if(x[i] != 1){
            ym[i] = y[i];
            w.insert( make_pair(i, i) );
        }
        else{
            if(x[i - 1] != 1){
                lst = i;
            }
            if(x[i + 1] != 1){
                w.insert( make_pair(lst, i) );
                aux = make_pair(0, 0);
                query(1, 1, n, lst, i);
                ym[lst] = aux.s;
            }
        }
	}
	return solve();
}
int updateX(int pos, int val) {
    pos++;
    set< pair<int, int> > :: iterator it;
    pair<int, int> a;
    if(x[pos] == 1){
        it = w.lower_bound( make_pair(pos + 1, 0) );
        it--;
        a = *it;
        w.erase(it);
        if(a.f != pos){
            w.insert( make_pair(a.f, pos - 1) );
            aux = make_pair(0, 0);
            query(1, 1, n, a.f, pos - 1);
            ym[a.f] = aux.s;
        }
        if(a.s != pos){
            w.insert( make_pair(pos + 1, a.s) );
            aux = make_pair(0, 0);
            query(1, 1, n, pos + 1, a.s);
            ym[pos + 1] = aux.s;
        }
        w.insert( make_pair(pos, pos) );
        ym[pos] = pos;
    }
    x[pos] = val;
    update(1, 1, n, pos);
    if(x[pos] == 1){
        w.erase( make_pair(pos, pos) );
        a = make_pair(pos, pos);
        if(x[pos - 1] == 1){
            it = w.lower_bound( make_pair(pos, pos) );
            it--;
            a.f = it->f;
            w.erase(it);
        }
        if(x[pos + 1] == 1){
            it = w.lower_bound( make_pair(pos, pos) );
            a.s = it->s;
            w.erase(it);
        }
        w.insert(a);
        aux = make_pair(0, 0);
        query(1, 1, n, a.f, a.s);
        ym[a.f] = aux.s;
    }
	return solve();
}
int updateY(int pos, int val) {
    pos++;
    y[pos] = val;
    update(1, 1, n, pos);
    set< pair<int, int> > :: iterator it;
    it = w.lower_bound( make_pair(pos + 1, 0) );
    it--;
    aux = make_pair(0, 0);
    query(1, 1, n, it->f, it->s);
    ym[it->f] = aux.s;
	return solve();
}

Compilation message (stderr)

horses.cpp: In function 'void build(int, int, int)':
horses.cpp:21:67: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         aint[nod].f = aint[2 * nod].f * 1LL * aint[2 * nod + 1].f % mod;
                                                                   ^
horses.cpp: In function 'void update(int, int, int, int)':
horses.cpp:37:67: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         aint[nod].f = aint[2 * nod].f * 1LL * aint[2 * nod + 1].f % mod;
                                                                   ^
horses.cpp: In function 'void query(int, int, int, int, int)':
horses.cpp:44:47: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
             aux.f = aux.f * 1LL * aint[nod].f % mod;
                                               ^
horses.cpp: In function 'int solve()':
horses.cpp:85:31: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return aux.f * 1LL * ymax % mod;
                               ^
horses.cpp:59:9: warning: unused variable 'i' [-Wunused-variable]
     int i, ind, ymax;
         ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:90:6: warning: declaration of 'lst' shadows a global declaration [-Wshadow]
  int lst;
      ^~~
horses.cpp:10:28: note: shadowed declaration is here
 static int x[DIM], y[DIM], lst[DIM], ym[DIM];
                            ^~~
horses.cpp: At global scope:
horses.cpp:10:28: warning: 'lst' defined but not used [-Wunused-variable]
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:109:25: warning: 'lst' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 ym[lst] = aux.s;
                         ^

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