oj.uz

Submission #874131

# Submission time Handle Problem Language Result Execution time Memory
874131 2023-11-16T09:47:12 Z HuyQuang_re_Zero Horses (IOI15_horses) C++14
34 / 100
 20 ms 12372 KB 
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#include "horses.h"
using namespace std;
const ll mod=round(1e9)+7;
set <int> s;
struct pt { ll x,y; };
pt operator + (pt a,pt b) { return { a.x*b.x%mod,max(a.y,b.y) }; }
int x[100005],y[100005],n,i,u,q,type,pos,val;
struct Interval_Tree
{
    pt st[4*500005];
    void update(int id,int l,int r,int u)
    {
        if(l==r) { st[id]={ x[u],y[u] }; return ; }
        int mid=(l+r)>>1;
        if(u<=mid) update(id*2,l,mid,u);
        else update(id*2+1,mid+1,r,u);
        st[id]=st[id*2]+st[id*2+1];
    }
    pt get(int id,int l,int r,int u,int v)
    {
        if(u>r || v<l) return { 1,0 };
        if(u<=l && r<=v) return st[id];
        int mid=(l+r)>>1;
        return get(id*2,l,mid,u,v)+get(id*2+1,mid+1,r,u,v);
    }
} IT;
int Cal()
{
    set <int>::iterator it=s.end();
    ll ma=0,res=0,last=n+1;
    while(it!=s.begin())
    {
        it--;
        int u=*it;
        ll k=IT.get(1,1,n,u,last-1).y;
        if(ma<k)
        {
            ma=k;
            res=IT.get(1,1,n,1,u).x*ma%mod;
        }
        ma=ma*x[u];
        if(ma>round(1e9)) break;
        last=u;
    }
    return res;
}
int init(int _n,int _x[],int _y[])
{
    n=_n;
    s.insert(0);
    for(i=n;i>=1;i--)
    {
        x[i]=_x[i-1],y[i]=_y[i-1];
        if(x[i]>=2) s.insert(i);
        IT.update(1,1,n,i);
    }
    x[0]=1;
    return Cal();
}
int updateX(int u,int k)
{
    u++;
    s.erase(u);
    x[u]=k;
    if(x[u]>=2) s.insert(u);
    IT.update(1,1,n,u);
    return Cal();
}
int updateY(int u,int k)
{
    u++;
    y[u]=k;
    IT.update(1,1,n,u);
    return Cal();
}
/*
int main()
{
    freopen("horse.inp","r",stdin);
    freopen("horse.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for(i=0;i<n;i++) cin>>x[i];
    for(i=0;i<n;i++) cin>>y[i];
    cout<<init(n,x,y)<<'\n';
    cin>>q;
    while(q--)
    {
        cin>>type>>pos>>val;
        if(type==1) cout<<updateX(pos,val)<<'\n';
        else cout<<updateY(pos,val)<<'\n';
    }
}
*/

Compilation message

horses.cpp: In member function 'void Interval_Tree::update(int, int, int, int)':
horses.cpp:26:40: warning: declaration of 'u' shadows a global declaration [-Wshadow]
   26 |     void update(int id,int l,int r,int u)
      |                                    ~~~~^
horses.cpp:22:29: note: shadowed declaration is here
   22 | int x[100005],y[100005],n,i,u,q,type,pos,val;
      |                             ^
horses.cpp: In member function 'pt Interval_Tree::get(int, int, int, int, int)':
horses.cpp:34:35: warning: declaration of 'u' shadows a global declaration [-Wshadow]
   34 |     pt get(int id,int l,int r,int u,int v)
      |                               ~~~~^
horses.cpp:22:29: note: shadowed declaration is here
   22 | int x[100005],y[100005],n,i,u,q,type,pos,val;
      |                             ^
horses.cpp: In function 'int Cal()':
horses.cpp:49:13: warning: declaration of 'u' shadows a global declaration [-Wshadow]
   49 |         int u=*it;
      |             ^
horses.cpp:22:29: note: shadowed declaration is here
   22 | int x[100005],y[100005],n,i,u,q,type,pos,val;
      |                             ^
horses.cpp:50:33: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   50 |         ll k=IT.get(1,1,n,u,last-1).y;
      |                             ~~~~^~
horses.cpp:57:12: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   57 |         if(ma>round(1e9)) break;
      |            ^~
horses.cpp:60:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   60 |     return res;
      |            ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:75:17: warning: declaration of 'u' shadows a global declaration [-Wshadow]
   75 | int updateX(int u,int k)
      |             ~~~~^
horses.cpp:22:29: note: shadowed declaration is here
   22 | int x[100005],y[100005],n,i,u,q,type,pos,val;
      |                             ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:84:17: warning: declaration of 'u' shadows a global declaration [-Wshadow]
   84 | int updateY(int u,int k)
      |             ~~~~^
horses.cpp:22:29: note: shadowed declaration is here
   22 | int x[100005],y[100005],n,i,u,q,type,pos,val;
      |                             ^

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 444 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 452 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 440 KB Output is correct
13 Correct 1 ms 440 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 440 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 3 ms 348 KB Output is correct
28 Correct 2 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 2 ms 348 KB Output is correct
32 Correct 2 ms 348 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 9828 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 440 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 444 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 2 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 2 ms 348 KB Output is correct
32 Correct 2 ms 348 KB Output is correct
33 Runtime error 20 ms 12372 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 444 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 392 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 416 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 352 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 3 ms 352 KB Output is correct
28 Correct 1 ms 352 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 2 ms 348 KB Output is correct
32 Correct 2 ms 348 KB Output is correct
33 Runtime error 13 ms 10584 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -