제출 #524133

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
524133		Lobo	말 (IOI15_horses)	C++17	100 / 100	1438 ms	73240 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 550000

int n, a[maxn], b[maxn], trmx[4*maxn], trp[4*maxn];
map<int,pair<int,int>> lr;
int mod = 1e9 + 7;
dbl logmax, logtot;

void attmx(int no, int l, int r, int pos, int val) {
    if(l > pos || r < pos) return;
    else if(l == r) trmx[no] = val;
    else {
        int f1 = 2*no;
        int f2 = 2*no + 1;
        int mid = (l+r)>>1;

        attmx(f1,l,mid,pos,val);
        attmx(f2,mid+1,r,pos,val);
        trmx[no] = max(trmx[f1],trmx[f2]);
    }
}

int qrmx(int no, int l, int r, int L, int R) {
    if(l > R || r < L) return 0;
    else if(l >= L && r <= R) return trmx[no];
    else {
        int f1 = 2*no;
        int f2 = 2*no + 1;
        int mid = (l+r)>>1;
        return max(qrmx(f1,l,mid,L,R),qrmx(f2,mid+1,r,L,R));
    }
}

void attp(int no, int l, int r, int pos, int val) {
    if(l > pos || r < pos) return;
    else if(l == r) trp[no] = val;
    else {
        int f1 = 2*no;
        int f2 = 2*no + 1;
        int mid = (l+r)>>1;

        attp(f1,l,mid,pos,val);
        attp(f2,mid+1,r,pos,val);
        trp[no] = (trp[f1]*trp[f2])%mod;
    }
}

int qrp(int no, int l, int r, int L, int R) {
    if(l > R || r < L) return 1;
    else if(l >= L && r <= R) return trp[no];
    else {
        int f1 = 2*no;
        int f2 = 2*no + 1;
        int mid = (l+r)>>1;
        return (qrp(f1,l,mid,L,R)*qrp(f2,mid+1,r,L,R))%mod;
    }
}

int qrr() {
    auto it = lr.end(); it--;

    dbl logcur = logtot;
    int ans = 0;
    dbl anslg = -inf;
    while(true) {
        int l = it->fr;
        int r = it->sc.fr;
        int p = it->sc.sc;
        int mx = qrmx(1,0,n-1,l,r);

        dbl anscur = log2(mx) + logcur;
        if(anscur >= anslg) {
            anslg = anscur;
            ans = (qrp(1,0,n-1,0,r)*mx)%mod;
        }

        logcur -= log2(p);
        if(logcur + logmax < logtot || it == lr.begin()) break;
        it--;
    }

    

    return ans;
}

int32_t init(int32_t N, int32_t X[], int32_t Y[]) {
    n = N;
    logtot = 0;
    logmax = 31;
    for(int i = 0; i < n; i++) {
        a[i] = X[i];
        logtot+= log2(a[i]);
        attp(1,0,n-1,i,a[i]);
    }

    for(int i = 0; i < n; i++) {
        b[i] = Y[i];
        attmx(1,0,n-1,i,b[i]);
    }

    for(int i = 0; i < n;) {
        if(a[i] != 1) {
            lr[i] = mp(i,a[i]);
            i++;
        }
        else {
            int ant = i;
            while(i < n && a[i] == 1) {
                i++;
            }
            lr[ant] = mp(i-1,1);
        }
    }

    return qrr();
}

int32_t updateX(int32_t pos, int32_t val) {
    if(val == a[pos]) {
        return qrr();
    }

    attp(1,0,n-1,pos,val);
    logtot-= log2(a[pos]);
    logtot+= log2(val);

    if(a[pos] != 1 && val != 1) {
        a[pos] = val;
        lr[pos] = mp(pos,val);
        return qrr();
    }

    auto it = lr.upper_bound(pos); it--;
    if(val == 1) {
        //quero pegar o cara da direita e da esquerda e juntar com esse
        vector<int> tir;
        int l = pos;
        int r = pos;
        if(it != lr.begin()) {
            it--;
            //tiro ele se for igual a 1
            if(it->sc.sc == 1) {
                l = it->fr;
                tir.pb(it->fr);
            }
            it++;
        }
        it++;
        if(it != lr.end()) {
            if(it->sc.sc == 1) {
                r = it->sc.fr;
                tir.pb(it->fr);
            }
        }
        it--;

        tir.pb(it->fr);

        for(auto x : tir) {
            lr.erase(x);
        }

        lr[l] = mp(r,1);
    }
    else {
        //quero pegar o cara da direita e da esquerda e separar

        int l = it->fr;
        int r = it->sc.fr;
        lr.erase(l);

        if(l != pos) {
            //inserir (l,pos-1)
            lr[l] = mp(pos-1,1);
        }
        lr[pos] = mp(pos,val);
        if(r != pos) {
            lr[pos+1] = mp(r,1);
        }
    }

    a[pos] = val;
    return qrr();

}

int32_t updateY(int32_t pos, int32_t val) {
    b[pos] = val;
    attmx(1,0,n-1,pos,val);
    return qrr();
}

컴파일 시 표준 에러 (stderr) 메시지

horses.cpp: In function 'int32_t init(int32_t, int32_t*, int32_t*)':
horses.cpp:130:15: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
  130 |     return qrr();
      |            ~~~^~
horses.cpp: In function 'int32_t updateX(int32_t, int32_t)':
horses.cpp:135:19: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
  135 |         return qrr();
      |                ~~~^~
horses.cpp:145:19: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
  145 |         return qrr();
      |                ~~~^~
horses.cpp:198:15: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
  198 |     return qrr();
      |            ~~~^~
horses.cpp: In function 'int32_t updateY(int32_t, int32_t)':
horses.cpp:205:15: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
  205 |     return qrr();
      |            ~~~^~

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