Submission #395137

#	Time	Username	Problem	Language	Result	Execution time	Memory
395137		andremfq	Horses (IOI15_horses)	C++17	100 / 100	923 ms	54264 KiB

horses

//ideia Leonardo
#include <bits/stdc++.h>
#include "horses.h"
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const int MAXN = 500001;
const int MOD = 1e9+7;
 
struct seg{
    ll id, v;
};
 
seg tree[4*MAXN];
ll mult[4*MAXN];
int *x, *y;
int n;
set<int> s; // todos os indices de x>=2
 
seg merge(seg a, seg b){
    if(a.v<b.v)
        return b;
    return a;
}
 
void build(int id, int l, int r){
    if(l==r){
        tree[id] = {l, y[l]};
        mult[id] = x[l];
        return;
    }
    int e = id*2+1;
    int d = id*2+2;
    int m = (l+r)>>1;
    build(e,l,m);
    build(d,m+1,r);
    tree[id] = merge(tree[e],tree[d]);
    mult[id] = (mult[e]*mult[d])%MOD;
}
 
void update(int id, int l, int r, int q){
    if(r< q || l > q){
        return;
    }
    if(l==q && r == q){
        tree[id] = {l,y[l]};
        return;
    }
    int e = id*2+1;
    int d = id*2+2;
    int m = (l+r)>>1;
    update(e,l,m,q);
    update(d,m+1,r,q);
    tree[id] = merge(tree[e],tree[d]);
}
 
seg query(int id, int l, int r, int ql, int qr){
    if(ql > r || qr < l || qr < ql)
        return {0,-1};
    if(ql <= l && r <= qr)
        return tree[id];
    int e = id*2+1;
    int d = id*2+2;
    int m = (l+r)>>1;
    return merge(query(e,l,m,ql,qr),query(d,m+1,r,ql,qr));
}
 
void updatemult(int id, int l, int r, int q){
    if(q < l || q > r)
        return;
    if(l==q && r ==q){
        mult[id] = x[l];
        return;
    }
    int e = id*2+1;
    int d = id*2+2;
    int m = (l+r)>>1;
    updatemult(e,l,m,q);
    updatemult(d,m+1,r,q);
    mult[id] = (mult[e]*mult[d])%MOD;
}
 
ll querymult(int id, int l, int r, int ql, int qr){
    if(ql > r || qr < l || qr < ql)
        return 1;
    if(ql <= l && r <= qr)
        return mult[id];
    int e = id*2+1;
    int d = id*2+2;
    int m = (l+r)>>1;
    return (querymult(e,l,m,ql,qr)*querymult(d,m+1,r,ql,qr))%MOD;
}
 
ll calc(){
    auto it = s.rbegin();
    //iterador reverso: começa na ultima posição e termina 1 a menos da primeira posição
 
    seg resp = {0,0};
    int r = n-1;
 
    while(true){
        if(it == s.rend()){ 
            resp = merge(resp, query(0,0,n-1,0,r));
            // compara a resposta atual com o bloco de 1 mais à esquerda
            break;
        }
        resp = merge(resp,query(0,0,n-1,*it,r));
        // compara a resposta atual com o próximo indice de x >= 2 e com o bloco de x = 1 à direita
        resp.v*= x[*it];
        r = *it-1;
        if(resp.v > (ll)1e9)
            break;
        it++;
    }
    return (querymult(0,0,n-1,0,resp.id) * y[resp.id]) % MOD;
}
 
int init(int N ,int X[], int Y[]){
    x = X; 
    y = Y;
    // o X[] e Y[] continuam sendo válidos mesmo depois da chamada da funcão então eu vou usar *x e *y pra acessar o array
    n = N;
    build(0,0,n-1);
    for(int i = 0; i < n; i++)
        if(x[i] >= 2)
            s.insert(i);
    return calc();
}  
 
int updateX(int pos, int val){
    s.erase(pos);
    x[pos] = val;
    if(x[pos]>=2)
        s.insert(pos);
    updatemult(0,0,n-1,pos);
    return calc();
}
 
int updateY(int pos, int val){
    y[pos] = val;
    update(0,0,n-1,pos);
    return calc();
}
 
/*int main(){
    int N, Q;
    cin >> N >> Q;
    int X[N], Y[N];
    for(int i = 0; i < N; i++)
        cin >> X[i];
    for(int i = 0; i < N; i++)
        cin >> Y[i];
    cout << init(N,X,Y) << '\n';
    for(int i = 0; i < Q; i++){
        int t, a, b;
        cin >> t >> a >> b;
        if(t){
            cout << updateY(a,b) << '\n';
        } else{
            cout << updateX(a,b) << '\n';
        }
    }
}*/

Compilation message (stderr)

horses.cpp: In function 'll calc()':
horses.cpp:122:38: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  122 |     return (querymult(0,0,n-1,0,resp.id) * y[resp.id]) % MOD;
      |                                 ~~~~~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:134:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  134 |     return calc();
      |            ~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:143:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  143 |     return calc();
      |            ~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:149:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  149 |     return calc();
      |            ~~~~^~

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