oj.uz

Submission #524135

# Submission time Handle Problem Language Result Execution time Memory
524135 2022-02-08T17:03:23 Z Lobo Horses (IOI15_horses) C++17
100 / 100
 1408 ms 62900 KB 
#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) {
    int val1 = val;
    if(val1 == a[pos]) {
        return qrr();
    }
 
    attp(1,0,n-1,pos,val1);
    logtot-= log2(a[pos]);
    logtot+= log2(val1);
 
    if(a[pos] != 1 && val1 != 1) {
        a[pos] = val1;
        lr[pos] = mp(pos,val);
        return qrr();
    }
 
    auto it = lr.upper_bound(pos); it--;
    if(val1 == 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,val1);
        if(r != pos) {
            lr[pos+1] = mp(r,1);
        }
    }
 
    a[pos] = val1;
    return qrr();
 
}
 
int32_t updateY(int32_t pos, int32_t val) {
    int val1 = val;
    b[pos] = val1;
    attmx(1,0,n-1,pos,val1);
    return qrr();
}

Compilation message

horses.cpp: In function 'int32_t init(int32_t, int32_t*, int32_t*)':
horses.cpp:128:15: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
  128 |     return qrr();
      |            ~~~^~
horses.cpp: In function 'int32_t updateX(int32_t, int32_t)':
horses.cpp:134:19: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
  134 |         return qrr();
      |                ~~~^~
horses.cpp:144:19: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
  144 |         return qrr();
      |                ~~~^~
horses.cpp:197:15: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
  197 |     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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 1 ms 300 KB Output is correct
18 Correct 0 ms 332 KB Output is correct
19 Correct 1 ms 304 KB Output is correct
20 Correct 1 ms 304 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 0 ms 292 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 308 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 0 ms 308 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 280 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 1 ms 300 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 0 ms 292 KB Output is correct
18 Correct 1 ms 304 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 308 KB Output is correct
21 Correct 0 ms 332 KB Output is correct
22 Correct 1 ms 296 KB Output is correct
23 Correct 2 ms 320 KB Output is correct
24 Correct 2 ms 316 KB Output is correct
25 Correct 3 ms 588 KB Output is correct
26 Correct 2 ms 440 KB Output is correct
27 Correct 6 ms 332 KB Output is correct
28 Correct 4 ms 460 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 2 ms 460 KB Output is correct
31 Correct 3 ms 332 KB Output is correct
32 Correct 8 ms 332 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 933 ms 61644 KB Output is correct
2 Correct 543 ms 61516 KB Output is correct
3 Correct 535 ms 61592 KB Output is correct
4 Correct 698 ms 62864 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 ms 284 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 308 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 304 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 1 ms 304 KB Output is correct
17 Correct 0 ms 332 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 0 ms 332 KB Output is correct
20 Correct 0 ms 304 KB Output is correct
21 Correct 0 ms 332 KB Output is correct
22 Correct 1 ms 304 KB Output is correct
23 Correct 2 ms 316 KB Output is correct
24 Correct 2 ms 332 KB Output is correct
25 Correct 3 ms 448 KB Output is correct
26 Correct 3 ms 460 KB Output is correct
27 Correct 7 ms 404 KB Output is correct
28 Correct 3 ms 460 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 2 ms 460 KB Output is correct
31 Correct 3 ms 332 KB Output is correct
32 Correct 7 ms 332 KB Output is correct
33 Correct 236 ms 30916 KB Output is correct
34 Correct 231 ms 30988 KB Output is correct
35 Correct 393 ms 61888 KB Output is correct
36 Correct 365 ms 61792 KB Output is correct
37 Correct 342 ms 30936 KB Output is correct
38 Correct 371 ms 61920 KB Output is correct
39 Correct 230 ms 30580 KB Output is correct
40 Correct 362 ms 61928 KB Output is correct
41 Correct 243 ms 30512 KB Output is correct
42 Correct 316 ms 30584 KB Output is correct
43 Correct 378 ms 61880 KB Output is correct
44 Correct 375 ms 61812 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 300 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 300 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 0 ms 332 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 2 ms 332 KB Output is correct
24 Correct 2 ms 332 KB Output is correct
25 Correct 3 ms 460 KB Output is correct
26 Correct 1 ms 460 KB Output is correct
27 Correct 6 ms 332 KB Output is correct
28 Correct 3 ms 460 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 2 ms 448 KB Output is correct
31 Correct 3 ms 316 KB Output is correct
32 Correct 7 ms 332 KB Output is correct
33 Correct 913 ms 62868 KB Output is correct
34 Correct 539 ms 62660 KB Output is correct
35 Correct 517 ms 62868 KB Output is correct
36 Correct 649 ms 62900 KB Output is correct
37 Correct 242 ms 31044 KB Output is correct
38 Correct 230 ms 30944 KB Output is correct
39 Correct 383 ms 61856 KB Output is correct
40 Correct 392 ms 61676 KB Output is correct
41 Correct 352 ms 30748 KB Output is correct
42 Correct 391 ms 61700 KB Output is correct
43 Correct 230 ms 30168 KB Output is correct
44 Correct 374 ms 61572 KB Output is correct
45 Correct 251 ms 30200 KB Output is correct
46 Correct 311 ms 30284 KB Output is correct
47 Correct 347 ms 61448 KB Output is correct
48 Correct 334 ms 61140 KB Output is correct
49 Correct 412 ms 33660 KB Output is correct
50 Correct 339 ms 33604 KB Output is correct
51 Correct 630 ms 61704 KB Output is correct
52 Correct 440 ms 61544 KB Output is correct
53 Correct 1408 ms 33092 KB Output is correct
54 Correct 677 ms 61164 KB Output is correct
55 Correct 352 ms 29328 KB Output is correct
56 Correct 477 ms 61124 KB Output is correct
57 Correct 594 ms 29736 KB Output is correct
58 Correct 1196 ms 29796 KB Output is correct
59 Correct 345 ms 59864 KB Output is correct