Submission #523612

#	Time	Username	Problem	Language	Result	Execution time	Memory
523612		Lobo	Horses (IOI15_horses)	C++17	Compilation error	0 ms	0 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 = 0;
    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;
}

int init(int N, int X[], int 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();
}

int updateX(int pos, int 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;
        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();

}

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

Compilation message (stderr)

/usr/bin/ld: /tmp/ccXuGJtN.o: in function `main':
grader.c:(.text.startup+0xaa): undefined reference to `init(int, int*, int*)'
/usr/bin/ld: grader.c:(.text.startup+0x113): undefined reference to `updateX(int, int)'
/usr/bin/ld: grader.c:(.text.startup+0x16d): undefined reference to `updateY(int, int)'
collect2: error: ld returned 1 exit status