oj.uz

Submission #522838

# Submission time Handle Problem Language Result Execution time Memory
522838 2022-02-06T01:32:52 Z Deepesson Horses (IOI15_horses) C++17
100 / 100
 1002 ms 83004 KB 
#include <bits/stdc++.h>
#include "horses.h"
#define MAX 505000
typedef long long ll;
typedef std::pair<ll,int> plb;

long long MOD = 1e9+7;
plb mul(plb a,plb b){
    plb c;
    c.first=a.first*b.first;
    c.second=a.second+b.second;
    if(c.first>=MOD){
        c.second++;
        c.first%=MOD;
    }
    return c;
}
typedef std::pair<plb,ll> ppi;
ll n;
ppi mul(ppi a,ppi b){
    plb c=mul(a.first,b.first);
    ppi d;
    d.first=c;
    d.second=a.second;
    return d;
}
ppi tab[MAX*4];

void update(int t,int j,int la=0,int ra=n-1,int pos=1){
    int m = (la+ra)/2;
    if(ra<t||la>t)return;
    if(la==ra){
        tab[pos].second=t;
        tab[pos].first.first=j;
        tab[pos].first.second=false;
        return;
    }
    update(t,j,la,m,pos*2);
    update(t,j,m+1,ra,(pos*2)+1);
    tab[pos]=mul(tab[pos*2],tab[(pos*2)+1]);
}
ppi omega;
ppi nrmquery(int l,int r,int la=0,int ra=n-1,int pos=1){
    if(l>ra||r<la)return omega;
    if(l<=la&&r>=ra){
        return tab[pos];
    }
    int m = (la+ra)/2;
    return mul(nrmquery(l,r,la,m,pos*2),nrmquery(l,r,m+1,ra,(pos*2)+1));
}

int query(int x){
    int l=0,r=x;
    while(l<r){
        int m = (l+r)/2;
        if(nrmquery(m,x).first.second){
            l=m+1;
        }else r=m;
    }
    return l;
}

typedef std::array<std::array<long long,2>,2> matriz;
matriz mul(matriz a,matriz b){
    matriz c={};
    for(int i=0;i!=2;++i){
        for(int j=0;j!=2;++j){
            for(int k=0;k!=2;++k){
                ///Nunca vai ter q usar o MOD, estou fazendo malandragem para isso
                c[i][j]=std::max(c[i][j],(a[i][k]*b[k][j]));
            }
        }
    }
    return c;
}
matriz mattab[MAX*4];
matriz neutro;
void matupdate(int t,matriz k,int la=0,int ra=n-1,int pos=1){
    if(ra<t||la>t)return;
    if(la==ra){
        mattab[pos]=k;
        return;
    }
    int m = (la+ra)/2;
    matupdate(t,k,la,m,pos*2);
    matupdate(t,k,m+1,ra,(pos*2)+1);
    mattab[pos]=mul(mattab[pos*2],mattab[(pos*2)+1]);
}
matriz matquery(int l,int r,int la=0,int ra=n-1,int pos=1){
    if(l>ra||r<la)return neutro;
    if(l<=la&&r>=ra){
        return mattab[pos];
    }
    int m = (la+ra)/2;
    return mul(matquery(l,r,la,m,pos*2),matquery(l,r,m+1,ra,(pos*2)+1));
}
matriz gerarmat(int X,int Y){
    matriz a={},b={};
    a[0][0]=X;
    a[1][1]=1;
    b[0][0]=1;
    b[1][1]=1;
    b[0][1]=Y;
    return mul(a,b);
}
ll x[MAX],y[MAX];
int get(int x=n-1){
    int l = query(x);
    long long base=1;
    if(l){
        auto u = nrmquery(0,l-1);
        base=u.first.first;
    }
    matriz a={};
    a[0][0]=base;
    matriz b = matquery(l,n-1);
    if(l){
        matriz g={};g[0][0]=1;
        matriz k=mul(g,b);
        long long rate = std::max(k[0][1],y[l-1]);
        rate%=MOD;
        return (rate*base)%MOD;
    }
    a=mul(a,b);
    return a[0][1]%MOD;
}
int init(int N, int X[], int Y[]) {
    omega.first.first=1;
    neutro[0][0]=neutro[1][1]=1;
    n=N;
    for(int i=0;i!=N;++i){
        update(i,X[i]);
    }
    for(int i=0;i!=N;++i){
        x[i]=X[i],y[i]=Y[i];
        matupdate(i,gerarmat(X[i],Y[i]));
    }
	return get();
}

int updateX(int pos, int val) {
    x[pos]=val;
    update(pos,val);
    matupdate(pos,gerarmat(x[pos],y[pos]));
	return get();
}

int updateY(int pos, int val) {
    y[pos]=val;
    matupdate(pos,gerarmat(x[pos],y[pos]));
	return get();
}

Compilation message

horses.cpp:29:42: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   29 | void update(int t,int j,int la=0,int ra=n-1,int pos=1){
      |                                         ~^~
horses.cpp:43:43: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   43 | ppi nrmquery(int l,int r,int la=0,int ra=n-1,int pos=1){
      |                                          ~^~
horses.cpp: In function 'int query(int)':
horses.cpp:56:24: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   56 |         if(nrmquery(m,x).first.second){
      |                        ^
horses.cpp: At global scope:
horses.cpp:78:48: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   78 | void matupdate(int t,matriz k,int la=0,int ra=n-1,int pos=1){
      |                                               ~^~
horses.cpp:89:46: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   89 | matriz matquery(int l,int r,int la=0,int ra=n-1,int pos=1){
      |                                             ~^~
horses.cpp:107:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  107 | int get(int x=n-1){
      |               ~^~
horses.cpp: In function 'int get(int)':
horses.cpp:107:13: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  107 | int get(int x=n-1){
      |         ~~~~^~~~~
horses.cpp:106:4: note: shadowed declaration is here
  106 | ll x[MAX],y[MAX];
      |    ^
horses.cpp:111:32: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  111 |         auto u = nrmquery(0,l-1);
      |                                ^
horses.cpp:116:28: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  116 |     matriz b = matquery(l,n-1);
      |                           ~^~
horses.cpp:116:30: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  116 |     matriz b = matquery(l,n-1);
      |                              ^
horses.cpp:122:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  122 |         return (rate*base)%MOD;
      |                ~~~~~~~~~~~^~~~
horses.cpp:125:19: warning: conversion from 'std::array<long long int, 2>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  125 |     return a[0][1]%MOD;
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:132:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  132 |         update(i,X[i]);
      |                      ^
horses.cpp:136:40: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  136 |         matupdate(i,gerarmat(X[i],Y[i]));
      |                                        ^
horses.cpp:138:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  138 |  return get();
      |             ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:143:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  143 |     update(pos,val);
      |                   ^
horses.cpp:144:33: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  144 |     matupdate(pos,gerarmat(x[pos],y[pos]));
      |                            ~~~~~^
horses.cpp:144:40: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  144 |     matupdate(pos,gerarmat(x[pos],y[pos]));
      |                                   ~~~~~^
horses.cpp:144:42: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  144 |     matupdate(pos,gerarmat(x[pos],y[pos]));
      |                                          ^
horses.cpp:145:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  145 |  return get();
      |             ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:150:33: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  150 |     matupdate(pos,gerarmat(x[pos],y[pos]));
      |                            ~~~~~^
horses.cpp:150:40: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  150 |     matupdate(pos,gerarmat(x[pos],y[pos]));
      |                                   ~~~~~^
horses.cpp:150:42: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  150 |     matupdate(pos,gerarmat(x[pos],y[pos]));
      |                                          ^
horses.cpp:151:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  151 |  return get();
      |             ^

Subtask #1
17.0 / 17.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 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 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 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 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 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 0 ms 204 KB Output is correct
23 Correct 3 ms 460 KB Output is correct
24 Correct 3 ms 460 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 3 ms 436 KB Output is correct
27 Correct 2 ms 460 KB Output is correct
28 Correct 3 ms 460 KB Output is correct
29 Correct 2 ms 436 KB Output is correct
30 Correct 3 ms 460 KB Output is correct
31 Correct 2 ms 460 KB Output is correct
32 Correct 2 ms 460 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 850 ms 70444 KB Output is correct
2 Correct 929 ms 70460 KB Output is correct
3 Correct 915 ms 74176 KB Output is correct
4 Correct 962 ms 78404 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 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 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 3 ms 460 KB Output is correct
24 Correct 3 ms 460 KB Output is correct
25 Correct 3 ms 428 KB Output is correct
26 Correct 3 ms 460 KB Output is correct
27 Correct 3 ms 460 KB Output is correct
28 Correct 3 ms 460 KB Output is correct
29 Correct 2 ms 460 KB Output is correct
30 Correct 3 ms 460 KB Output is correct
31 Correct 2 ms 440 KB Output is correct
32 Correct 2 ms 460 KB Output is correct
33 Correct 453 ms 73516 KB Output is correct
34 Correct 444 ms 73448 KB Output is correct
35 Correct 470 ms 80452 KB Output is correct
36 Correct 473 ms 80336 KB Output is correct
37 Correct 441 ms 71768 KB Output is correct
38 Correct 436 ms 72516 KB Output is correct
39 Correct 427 ms 71572 KB Output is correct
40 Correct 452 ms 75576 KB Output is correct
41 Correct 424 ms 71576 KB Output is correct
42 Correct 432 ms 71596 KB Output is correct
43 Correct 421 ms 75816 KB Output is correct
44 Correct 411 ms 75884 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 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 216 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 0 ms 276 KB Output is correct
23 Correct 3 ms 464 KB Output is correct
24 Correct 3 ms 480 KB Output is correct
25 Correct 3 ms 460 KB Output is correct
26 Correct 3 ms 460 KB Output is correct
27 Correct 3 ms 436 KB Output is correct
28 Correct 3 ms 428 KB Output is correct
29 Correct 3 ms 460 KB Output is correct
30 Correct 3 ms 460 KB Output is correct
31 Correct 2 ms 460 KB Output is correct
32 Correct 3 ms 460 KB Output is correct
33 Correct 837 ms 74208 KB Output is correct
34 Correct 996 ms 83004 KB Output is correct
35 Correct 918 ms 74236 KB Output is correct
36 Correct 1002 ms 78048 KB Output is correct
37 Correct 456 ms 73692 KB Output is correct
38 Correct 439 ms 73412 KB Output is correct
39 Correct 465 ms 80488 KB Output is correct
40 Correct 468 ms 80592 KB Output is correct
41 Correct 430 ms 71620 KB Output is correct
42 Correct 423 ms 72576 KB Output is correct
43 Correct 428 ms 71472 KB Output is correct
44 Correct 440 ms 75480 KB Output is correct
45 Correct 409 ms 71620 KB Output is correct
46 Correct 432 ms 71876 KB Output is correct
47 Correct 401 ms 75844 KB Output is correct
48 Correct 412 ms 75936 KB Output is correct
49 Correct 932 ms 75424 KB Output is correct
50 Correct 895 ms 75424 KB Output is correct
51 Correct 883 ms 82356 KB Output is correct
52 Correct 858 ms 81732 KB Output is correct
53 Correct 898 ms 73880 KB Output is correct
54 Correct 871 ms 74412 KB Output is correct
55 Correct 770 ms 72640 KB Output is correct
56 Correct 864 ms 77404 KB Output is correct
57 Correct 742 ms 73284 KB Output is correct
58 Correct 799 ms 73832 KB Output is correct
59 Correct 393 ms 75872 KB Output is correct