oj.uz

Submission #91037

# Submission time Handle Problem Language Result Execution time Memory
91037 2018-12-25T17:06:37 Z faustaadp Horses (IOI15_horses) C++17
100 / 100
 865 ms 269016 KB 
#include "horses.h"
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll i,has=0,hz=1,x[505050],y[505050],PS=1,mo=1000000007,K,n;
ll ST[2020202],ST2[2020202],te,a[505050],ST3[2020202];
void upd(ll aa,ll bb,ll cc,ll dd,ll ee)
{
    if(aa==bb)
        ST[ee]=dd;
    else
    {
        ll ce=(aa+bb)/2;
        if(cc<=ce)upd(aa,ce,cc,dd,ee*2);
        else upd(ce+1,bb,cc,dd,ee*2+1);
        ST[ee]=(ST[ee*2]*ST[ee*2+1])%mo;
    }
}
void upd2(ll aa,ll bb,ll cc,ll dd,ll ee)
{
    if(aa==bb)
        ST2[ee]=dd;
    else
    {
        ll ce=(aa+bb)/2;
        if(cc<=ce)upd2(aa,ce,cc,dd,ee*2);
        else upd2(ce+1,bb,cc,dd,ee*2+1);
        ST2[ee]=(ST2[ee*2]+ST2[ee*2+1]);
    }
}
void upd3(ll aa,ll bb,ll cc,ll dd,ll ee)
{
    if(aa==bb)
        ST3[ee]=dd;
    else
    {
        ll ce=(aa+bb)/2;
        if(cc<=ce)upd3(aa,ce,cc,dd,ee*2);
        else upd3(ce+1,bb,cc,dd,ee*2+1);
        ST3[ee]=max(ST3[ee*2],ST3[ee*2+1]);
    }
}
ll cari(ll aa,ll bb,ll cc,ll ee)
{
    if(aa==bb)
    {
        a[++te]=aa;
    }
    else
    {
        ll ce=(aa+bb)/2;
        if(ST2[ee*2+1]==0)
            cari(aa,ce,cc,ee*2);
        else
        {
            if(cc<=ST2[ee*2+1])cari(ce+1,bb,cc,ee*2+1);
            else
            {
                cari(aa,ce,cc-ST2[ee*2+1],ee*2);
                cari(ce+1,bb,ST2[ee*2+1],ee*2+1);
            }
        }

    }
}
ll que(ll aa,ll bb,ll cc,ll dd,ll ee)
{
    if(bb<cc||dd<aa)return 1LL;
    else if(cc<=aa&&bb<=dd)return ST[ee];
    else
    {
        ll ce=(aa+bb)/2;
        return (que(aa,ce,cc,dd,ee*2)*que(ce+1,bb,cc,dd,ee*2+1))%mo;
    }
}
ll que3(ll aa,ll bb,ll cc,ll dd,ll ee)
{
    if(bb<cc||dd<aa)return 0LL;
    else if(cc<=aa&&bb<=dd)return ST3[ee];
    else
    {
        ll ce=(aa+bb)/2;
        return max(que3(aa,ce,cc,dd,ee*2),que3(ce+1,bb,cc,dd,ee*2+1));
    }
}
ll powo(ll aa,ll bb)
{
    if(bb==0)return 1LL;
    else
    {
        ll tem=powo(aa,bb/2);
        tem=(tem*tem)%mo;
        if(bb%2==1)tem=(tem*aa)%mo;
        return tem;
    }
}
ll com(ll aa,ll bb)
{
    return (que(0,n-1,0,aa,1)*bb)%mo;
}
ll jaw()
{
    te=0;
    //memset(a,-1,sizeof(a));
    cari(0,n-1,min(32LL,ST2[1]),1);
   // sort(a+1)
    ll opt=a[te],hz=y[a[te]],ii,Z=x[a[te]];
    //for(ii=1;ii<=te;ii++)   cout<<ii<<" "<<a[ii]<<"\n";
    for(ii=te-1;ii>=1;ii--)
    {
        if(Z>1000000000)return com(opt,hz);
        //cout<<que3(0,n-1,a[ii],a[ii+1]-1,1)<<"\n";
        if(que3(0,n-1,a[ii],a[ii+1]-1,1)>Z*hz)
        {
            opt=a[ii];
            hz=que3(0,n-1,a[ii],a[ii+1]-1,1);
            Z=1;
        }
        Z*=x[a[ii]];
    }
    return com(opt,hz);
}
int init(int N, int X[], int Y[])
{
    n=N;
    for(i=0;i<N;i++)x[i]=X[i];
    for(i=0;i<N;i++)upd(0,n-1,i,x[i],1);
    for(i=0;i<N;i++)upd2(0,n-1,i,((x[i]>1)||(i==0||i==(n-1))),1);
    for(i=0;i<N;i++)y[i]=Y[i];
    for(i=0;i<N;i++)upd3(0,n-1,i,y[i],1);
    //K=max(0LL,n-32LL);
    K=0;
	return jaw();
}

int updateX(int pos, int val)
{
    upd(0,n-1,pos,val,1);
    upd2(0,n-1,pos,((val>1)||(pos==0||pos==(n-1))),1);
    x[pos]=val;
	return jaw();
}

int updateY(int pos, int val)
{
    y[pos]=val;
    upd3(0,n-1,pos,val,1);
	return jaw();
}

Compilation message

horses.cpp: In function 'long long int cari(long long int, long long int, long long int, long long int)':
horses.cpp:69:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
horses.cpp: In function 'long long int jaw()':
horses.cpp:111:18: warning: declaration of 'hz' shadows a global declaration [-Wshadow]
     ll opt=a[te],hz=y[a[te]],ii,Z=x[a[te]];
                  ^~
horses.cpp:9:12: note: shadowed declaration is here
 ll i,has=0,hz=1,x[505050],y[505050],PS=1,mo=1000000007,K,n;
            ^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:137:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return jaw();
         ~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:145:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return jaw();
         ~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:152:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return jaw();
         ~~~^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 636 KB Output is correct
3 Correct 2 ms 748 KB Output is correct
4 Correct 2 ms 756 KB Output is correct
5 Correct 2 ms 756 KB Output is correct
6 Correct 2 ms 756 KB Output is correct
7 Correct 2 ms 764 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 2 ms 772 KB Output is correct
10 Correct 2 ms 780 KB Output is correct
11 Correct 2 ms 784 KB Output is correct
12 Correct 2 ms 788 KB Output is correct
13 Correct 2 ms 792 KB Output is correct
14 Correct 2 ms 1012 KB Output is correct
15 Correct 2 ms 1012 KB Output is correct
16 Correct 2 ms 1012 KB Output is correct
17 Correct 2 ms 1012 KB Output is correct
18 Correct 2 ms 1012 KB Output is correct
19 Correct 2 ms 1012 KB Output is correct
20 Correct 2 ms 1012 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1012 KB Output is correct
2 Correct 2 ms 1012 KB Output is correct
3 Correct 2 ms 1012 KB Output is correct
4 Correct 2 ms 1012 KB Output is correct
5 Correct 2 ms 1012 KB Output is correct
6 Correct 2 ms 1012 KB Output is correct
7 Correct 2 ms 1012 KB Output is correct
8 Correct 2 ms 1012 KB Output is correct
9 Correct 2 ms 1012 KB Output is correct
10 Correct 2 ms 1012 KB Output is correct
11 Correct 2 ms 1012 KB Output is correct
12 Correct 2 ms 1012 KB Output is correct
13 Correct 2 ms 1012 KB Output is correct
14 Correct 2 ms 1012 KB Output is correct
15 Correct 2 ms 1012 KB Output is correct
16 Correct 2 ms 1012 KB Output is correct
17 Correct 2 ms 1012 KB Output is correct
18 Correct 2 ms 1016 KB Output is correct
19 Correct 2 ms 1020 KB Output is correct
20 Correct 2 ms 1028 KB Output is correct
21 Correct 2 ms 1028 KB Output is correct
22 Correct 2 ms 1036 KB Output is correct
23 Correct 3 ms 1168 KB Output is correct
24 Correct 3 ms 1204 KB Output is correct
25 Correct 3 ms 1224 KB Output is correct
26 Correct 3 ms 1272 KB Output is correct
27 Correct 4 ms 1272 KB Output is correct
28 Correct 3 ms 1316 KB Output is correct
29 Correct 3 ms 1316 KB Output is correct
30 Correct 3 ms 1344 KB Output is correct
31 Correct 4 ms 1344 KB Output is correct
32 Correct 4 ms 1344 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 779 ms 42496 KB Output is correct
2 Correct 495 ms 55164 KB Output is correct
3 Correct 520 ms 58840 KB Output is correct
4 Correct 571 ms 66540 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 66540 KB Output is correct
2 Correct 2 ms 66540 KB Output is correct
3 Correct 2 ms 66540 KB Output is correct
4 Correct 2 ms 66540 KB Output is correct
5 Correct 2 ms 66540 KB Output is correct
6 Correct 2 ms 66540 KB Output is correct
7 Correct 2 ms 66540 KB Output is correct
8 Correct 2 ms 66540 KB Output is correct
9 Correct 2 ms 66540 KB Output is correct
10 Correct 2 ms 66540 KB Output is correct
11 Correct 2 ms 66540 KB Output is correct
12 Correct 2 ms 66540 KB Output is correct
13 Correct 2 ms 66540 KB Output is correct
14 Correct 2 ms 66540 KB Output is correct
15 Correct 2 ms 66540 KB Output is correct
16 Correct 2 ms 66540 KB Output is correct
17 Correct 2 ms 66540 KB Output is correct
18 Correct 2 ms 66540 KB Output is correct
19 Correct 2 ms 66540 KB Output is correct
20 Correct 2 ms 66540 KB Output is correct
21 Correct 2 ms 66540 KB Output is correct
22 Correct 2 ms 66540 KB Output is correct
23 Correct 3 ms 66540 KB Output is correct
24 Correct 3 ms 66540 KB Output is correct
25 Correct 3 ms 66540 KB Output is correct
26 Correct 3 ms 66540 KB Output is correct
27 Correct 5 ms 66540 KB Output is correct
28 Correct 4 ms 66540 KB Output is correct
29 Correct 3 ms 66540 KB Output is correct
30 Correct 3 ms 66540 KB Output is correct
31 Correct 4 ms 66540 KB Output is correct
32 Correct 4 ms 66540 KB Output is correct
33 Correct 362 ms 69812 KB Output is correct
34 Correct 355 ms 73720 KB Output is correct
35 Correct 379 ms 84760 KB Output is correct
36 Correct 373 ms 95548 KB Output is correct
37 Correct 387 ms 97552 KB Output is correct
38 Correct 360 ms 100620 KB Output is correct
39 Correct 340 ms 102528 KB Output is correct
40 Correct 358 ms 108584 KB Output is correct
41 Correct 358 ms 110632 KB Output is correct
42 Correct 378 ms 112756 KB Output is correct
43 Correct 345 ms 118688 KB Output is correct
44 Correct 343 ms 125172 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 125172 KB Output is correct
2 Correct 2 ms 125172 KB Output is correct
3 Correct 2 ms 125172 KB Output is correct
4 Correct 2 ms 125172 KB Output is correct
5 Correct 2 ms 125172 KB Output is correct
6 Correct 2 ms 125172 KB Output is correct
7 Correct 2 ms 125172 KB Output is correct
8 Correct 2 ms 125172 KB Output is correct
9 Correct 2 ms 125172 KB Output is correct
10 Correct 2 ms 125172 KB Output is correct
11 Correct 2 ms 125172 KB Output is correct
12 Correct 2 ms 125172 KB Output is correct
13 Correct 2 ms 125172 KB Output is correct
14 Correct 2 ms 125172 KB Output is correct
15 Correct 2 ms 125172 KB Output is correct
16 Correct 2 ms 125172 KB Output is correct
17 Correct 2 ms 125172 KB Output is correct
18 Correct 2 ms 125172 KB Output is correct
19 Correct 2 ms 125172 KB Output is correct
20 Correct 2 ms 125172 KB Output is correct
21 Correct 2 ms 125172 KB Output is correct
22 Correct 2 ms 125172 KB Output is correct
23 Correct 3 ms 125172 KB Output is correct
24 Correct 3 ms 125172 KB Output is correct
25 Correct 3 ms 125172 KB Output is correct
26 Correct 3 ms 125172 KB Output is correct
27 Correct 5 ms 125172 KB Output is correct
28 Correct 4 ms 125172 KB Output is correct
29 Correct 3 ms 125172 KB Output is correct
30 Correct 3 ms 125172 KB Output is correct
31 Correct 4 ms 125172 KB Output is correct
32 Correct 4 ms 125172 KB Output is correct
33 Correct 788 ms 130152 KB Output is correct
34 Correct 512 ms 142088 KB Output is correct
35 Correct 516 ms 145740 KB Output is correct
36 Correct 588 ms 153492 KB Output is correct
37 Correct 368 ms 156416 KB Output is correct
38 Correct 352 ms 160408 KB Output is correct
39 Correct 377 ms 170252 KB Output is correct
40 Correct 374 ms 181104 KB Output is correct
41 Correct 389 ms 183276 KB Output is correct
42 Correct 363 ms 186300 KB Output is correct
43 Correct 343 ms 188328 KB Output is correct
44 Correct 358 ms 194224 KB Output is correct
45 Correct 358 ms 196132 KB Output is correct
46 Correct 382 ms 197068 KB Output is correct
47 Correct 346 ms 203432 KB Output is correct
48 Correct 353 ms 209816 KB Output is correct
49 Correct 579 ms 215904 KB Output is correct
50 Correct 486 ms 220916 KB Output is correct
51 Correct 556 ms 231372 KB Output is correct
52 Correct 438 ms 242696 KB Output is correct
53 Correct 865 ms 245280 KB Output is correct
54 Correct 591 ms 249176 KB Output is correct
55 Correct 465 ms 251544 KB Output is correct
56 Correct 473 ms 259144 KB Output is correct
57 Correct 639 ms 260264 KB Output is correct
58 Correct 807 ms 263604 KB Output is correct
59 Correct 345 ms 269016 KB Output is correct