oj.uz

Submission #72975

# Submission time Handle Problem Language Result Execution time Memory
72975 2018-08-27T11:38:40 Z edisonhello Horses (IOI15_horses) C++14
100 / 100
 1166 ms 174344 KB 
#include<bits/stdc++.h>
using namespace std;

const int mod=1000000007;

#define data pair<long double,int>
#define X first
#define Y second

data operator+(const data &a,const data &b){ return data(a.X+b.X,1ll*a.Y*b.Y%mod); }
/* struct data{
    double lg;
    int ans;
    data():lg(0),ans(1){}
    data(double v1,int v2):lg(v1),ans(v2);
    void reset(){ lg=0; ans=1; }
    data operator+(const data &b)const{ return data(lg+a.lg,1ll*ans*a.ans%mod); }
}; */

struct node{
    node *l,*r;
    // data v,tag,mx;
    data v,tag;
    void addtag(data z){ v=v+z; tag=tag+z; }
    void push(){ l->addtag(tag); r->addtag(tag); tag=data(0,1); }
    void pull(){ v=max(l->v,r->v); }
    node():l(0),r(0),v(0,1),tag(0,1){}
} *root;

int n,*x,*y;

int pw(int b,int n,int m,int a=1){
    if(!n)return a;
    if(n&1)return pw(1ll*b*b%m,n>>1,m,1ll*a*b%m);
    else return pw(1ll*b*b%m,n>>1,m,a);
}
int inv(int x){ return pw(x,mod-2,mod); }

data make(int v){ return data(log(v),v); }
data makei(int v){ return data(-log(v),inv(v)); }

#define mid ((l+r)>>1)
void build(node *now,int l,int r){
    if(l==r){
        now->v=make(y[l]);
        return;
    }
    build(now->l=new node(),l,mid);
    build(now->r=new node(),mid+1,r);
    now->pull();
}
void modify(node *now,int l,int r,int ml,int mr,data v){
    if(r<ml || mr<l)return;
    if(ml<=l&&r<=mr){
        now->addtag(v);
        return;
    }
    now->push();
    modify(now->l,l,mid,ml,mr,v);
    modify(now->r,mid+1,r,ml,mr,v);
    now->pull();
}

int init(int _n,int _x[],int _y[]){ 
    n=_n; x=_x; y=_y;
    build(root=new node(),0,n-1);
    // cout<<"init: "<<root->v.Y<<endl;
    data pre(0,1);
    for(int i=0;i<n;++i)pre=pre+make(x[i]),modify(root,0,n-1,i,i,pre);
    return root->v.Y;
}
int updateX(int pos,int val){
    modify(root,0,n-1,pos,n-1,makei(x[pos]));
    x[pos]=val;
    modify(root,0,n-1,pos,n-1,make(x[pos]));
    return root->v.Y;
}
int updateY(int pos,int val){
    modify(root,0,n-1,pos,pos,makei(y[pos]));
    y[pos]=val;
    modify(root,0,n-1,pos,pos,make(y[pos]));
    return root->v.Y;
}

#ifdef WEAK
int _x[500005],_y[500005];
int main(){
    int n; cin>>n;
    for(int i=0;i<n;++i)cin>>_x[i];
    for(int i=0;i<n;++i)cin>>_y[i];
    cout<<init(n,_x,_y)<<endl;
    int q; cin>>q; while(q--){
        int t,p,v; cin>>t>>p>>v;
        if(t==1)cout<<updateX(p,v)<<endl;
        else cout<<updateY(p,v)<<endl;
    }
}
#endif

Compilation message

horses.cpp: In function 'int pw(int, int, int, int)':
horses.cpp:32:33: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 int pw(int b,int n,int m,int a=1){
                                 ^
horses.cpp:30:5: note: shadowed declaration is here
 int n,*x,*y;
     ^
horses.cpp:34:29: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     if(n&1)return pw(1ll*b*b%m,n>>1,m,1ll*a*b%m);
                      ~~~~~~~^~
horses.cpp:34:46: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     if(n&1)return pw(1ll*b*b%m,n>>1,m,1ll*a*b%m);
                                       ~~~~~~~^~
horses.cpp:35:27: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     else return pw(1ll*b*b%m,n>>1,m,a);
                    ~~~~~~~^~
horses.cpp: In function 'int inv(int)':
horses.cpp:37:14: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 int inv(int x){ return pw(x,mod-2,mod); }
              ^
horses.cpp:30:8: note: shadowed declaration is here
 int n,*x,*y;
        ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 516 KB Output is correct
5 Correct 2 ms 516 KB Output is correct
6 Correct 2 ms 536 KB Output is correct
7 Correct 3 ms 536 KB Output is correct
8 Correct 2 ms 536 KB Output is correct
9 Correct 2 ms 536 KB Output is correct
10 Correct 2 ms 572 KB Output is correct
11 Correct 3 ms 572 KB Output is correct
12 Correct 2 ms 572 KB Output is correct
13 Correct 2 ms 572 KB Output is correct
14 Correct 2 ms 572 KB Output is correct
15 Correct 2 ms 572 KB Output is correct
16 Correct 2 ms 572 KB Output is correct
17 Correct 2 ms 572 KB Output is correct
18 Correct 2 ms 644 KB Output is correct
19 Correct 2 ms 644 KB Output is correct
20 Correct 2 ms 644 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 644 KB Output is correct
2 Correct 2 ms 644 KB Output is correct
3 Correct 3 ms 644 KB Output is correct
4 Correct 2 ms 644 KB Output is correct
5 Correct 3 ms 644 KB Output is correct
6 Correct 3 ms 644 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Correct 2 ms 644 KB Output is correct
9 Correct 2 ms 644 KB Output is correct
10 Correct 3 ms 644 KB Output is correct
11 Correct 3 ms 644 KB Output is correct
12 Correct 3 ms 644 KB Output is correct
13 Correct 2 ms 644 KB Output is correct
14 Correct 3 ms 644 KB Output is correct
15 Correct 2 ms 644 KB Output is correct
16 Correct 3 ms 644 KB Output is correct
17 Correct 2 ms 644 KB Output is correct
18 Correct 3 ms 644 KB Output is correct
19 Correct 2 ms 644 KB Output is correct
20 Correct 2 ms 644 KB Output is correct
21 Correct 2 ms 644 KB Output is correct
22 Correct 3 ms 644 KB Output is correct
23 Correct 7 ms 768 KB Output is correct
24 Correct 8 ms 792 KB Output is correct
25 Correct 5 ms 816 KB Output is correct
26 Correct 6 ms 872 KB Output is correct
27 Correct 5 ms 872 KB Output is correct
28 Correct 5 ms 872 KB Output is correct
29 Correct 4 ms 872 KB Output is correct
30 Correct 5 ms 872 KB Output is correct
31 Correct 4 ms 896 KB Output is correct
32 Correct 5 ms 900 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 768 ms 99500 KB Output is correct
2 Correct 962 ms 99520 KB Output is correct
3 Correct 1066 ms 99640 KB Output is correct
4 Correct 989 ms 99640 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 99640 KB Output is correct
2 Correct 3 ms 99640 KB Output is correct
3 Correct 3 ms 99640 KB Output is correct
4 Correct 3 ms 99640 KB Output is correct
5 Correct 2 ms 99640 KB Output is correct
6 Correct 3 ms 99640 KB Output is correct
7 Correct 3 ms 99640 KB Output is correct
8 Correct 3 ms 99640 KB Output is correct
9 Correct 3 ms 99640 KB Output is correct
10 Correct 3 ms 99640 KB Output is correct
11 Correct 2 ms 99640 KB Output is correct
12 Correct 3 ms 99640 KB Output is correct
13 Correct 2 ms 99640 KB Output is correct
14 Correct 2 ms 99640 KB Output is correct
15 Correct 4 ms 99640 KB Output is correct
16 Correct 2 ms 99640 KB Output is correct
17 Correct 3 ms 99640 KB Output is correct
18 Correct 2 ms 99640 KB Output is correct
19 Correct 2 ms 99640 KB Output is correct
20 Correct 2 ms 99640 KB Output is correct
21 Correct 3 ms 99640 KB Output is correct
22 Correct 2 ms 99640 KB Output is correct
23 Correct 5 ms 99640 KB Output is correct
24 Correct 5 ms 99640 KB Output is correct
25 Correct 5 ms 99640 KB Output is correct
26 Correct 4 ms 99640 KB Output is correct
27 Correct 4 ms 99640 KB Output is correct
28 Correct 4 ms 99640 KB Output is correct
29 Correct 5 ms 99640 KB Output is correct
30 Correct 5 ms 99640 KB Output is correct
31 Correct 5 ms 99640 KB Output is correct
32 Correct 6 ms 99640 KB Output is correct
33 Correct 738 ms 99640 KB Output is correct
34 Correct 686 ms 99640 KB Output is correct
35 Correct 648 ms 99640 KB Output is correct
36 Correct 624 ms 99640 KB Output is correct
37 Correct 658 ms 99640 KB Output is correct
38 Correct 642 ms 99640 KB Output is correct
39 Correct 571 ms 99640 KB Output is correct
40 Correct 667 ms 99640 KB Output is correct
41 Correct 626 ms 99640 KB Output is correct
42 Correct 572 ms 99640 KB Output is correct
43 Correct 583 ms 99640 KB Output is correct
44 Correct 685 ms 104928 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 104928 KB Output is correct
2 Correct 2 ms 104928 KB Output is correct
3 Correct 3 ms 104928 KB Output is correct
4 Correct 3 ms 104928 KB Output is correct
5 Correct 2 ms 104928 KB Output is correct
6 Correct 3 ms 104928 KB Output is correct
7 Correct 2 ms 104928 KB Output is correct
8 Correct 3 ms 104928 KB Output is correct
9 Correct 3 ms 104928 KB Output is correct
10 Correct 2 ms 104928 KB Output is correct
11 Correct 2 ms 104928 KB Output is correct
12 Correct 2 ms 104928 KB Output is correct
13 Correct 2 ms 104928 KB Output is correct
14 Correct 2 ms 104928 KB Output is correct
15 Correct 2 ms 104928 KB Output is correct
16 Correct 2 ms 104928 KB Output is correct
17 Correct 3 ms 104928 KB Output is correct
18 Correct 3 ms 104928 KB Output is correct
19 Correct 3 ms 104928 KB Output is correct
20 Correct 3 ms 104928 KB Output is correct
21 Correct 3 ms 104928 KB Output is correct
22 Correct 2 ms 104928 KB Output is correct
23 Correct 6 ms 104928 KB Output is correct
24 Correct 6 ms 104928 KB Output is correct
25 Correct 7 ms 104928 KB Output is correct
26 Correct 5 ms 104928 KB Output is correct
27 Correct 5 ms 104928 KB Output is correct
28 Correct 4 ms 104928 KB Output is correct
29 Correct 4 ms 104928 KB Output is correct
30 Correct 5 ms 104928 KB Output is correct
31 Correct 6 ms 104928 KB Output is correct
32 Correct 5 ms 104928 KB Output is correct
33 Correct 765 ms 106140 KB Output is correct
34 Correct 1077 ms 106140 KB Output is correct
35 Correct 995 ms 106140 KB Output is correct
36 Correct 947 ms 106140 KB Output is correct
37 Correct 672 ms 106140 KB Output is correct
38 Correct 616 ms 106140 KB Output is correct
39 Correct 655 ms 106140 KB Output is correct
40 Correct 644 ms 106140 KB Output is correct
41 Correct 598 ms 106140 KB Output is correct
42 Correct 600 ms 106140 KB Output is correct
43 Correct 569 ms 106140 KB Output is correct
44 Correct 675 ms 106140 KB Output is correct
45 Correct 555 ms 106140 KB Output is correct
46 Correct 573 ms 106140 KB Output is correct
47 Correct 554 ms 106140 KB Output is correct
48 Correct 553 ms 111440 KB Output is correct
49 Correct 954 ms 117576 KB Output is correct
50 Correct 1022 ms 122452 KB Output is correct
51 Correct 865 ms 134288 KB Output is correct
52 Correct 818 ms 145688 KB Output is correct
53 Correct 1166 ms 149192 KB Output is correct
54 Correct 812 ms 153048 KB Output is correct
55 Correct 713 ms 155256 KB Output is correct
56 Correct 786 ms 162908 KB Output is correct
57 Correct 788 ms 165752 KB Output is correct
58 Correct 801 ms 169020 KB Output is correct
59 Correct 567 ms 174344 KB Output is correct