oj.uz

Submission #761913

# Submission time Handle Problem Language Result Execution time Memory
761913 2023-06-20T11:28:52 Z Ahmed57 Horses (IOI15_horses) C++17
54 / 100
 966 ms 88520 KB 
#include <bits/stdc++.h>
using namespace std;
long long mod = 1000000007;
//Fast
long long fast(long long a,long long b){
    if(b==0)return 1;
    if(b==1)return a%mod;
    long long ha = fast(a,b/2)%mod;
    if(b%2==0)return (ha*ha)%mod;
    else return (((ha*ha)%mod)*a)%mod;
}
long long seg[2000001],lazy[2000001];
double seg2[2000001],lazy2[2000001];
void prop(int p,int l,int r){
    seg[p]*=lazy[p];
    seg[p]%=mod;
    seg2[p]+=lazy2[p];
    if(l!=r){
        lazy[p*2]*=lazy[p];
        lazy[p*2]%=mod;
        lazy2[p*2]+=lazy2[p];
        lazy[p*2+1]*=lazy[p];
        lazy[p*2+1]%=mod;
        lazy2[p*2+1]+=lazy2[p];
    }
    lazy[p] = 1;
    lazy2[p] = 0;
}
void update(int p,int l,int r,int lq,int rq,long long val,double val2){
    prop(p,l,r);
    if(l>=lq&&r<=rq){
        lazy[p]*=val;
        lazy[p]%=mod;
        lazy2[p]+=val2;
        prop(p,l,r);
        return ;
    }
    if(l>rq||r<lq)return ;
    int md = (l+r)/2;
    update(p*2,l,md,lq,rq,val,val2);
    update(p*2+1,md+1,r,lq,rq,val,val2);
    if(seg2[p*2]>seg2[p*2+1]){
        seg2[p]= seg2[p*2];
        seg[p] = seg[p*2];
    }else{
        seg2[p]= seg2[p*2+1];
        seg[p] = seg[p*2+1];
    }
}
pair<long long,double> query(int p,int l,int r,int lq,int rq){
    prop(p,l,r);
    if(l>=lq&&r<=rq)return {seg[p],seg2[p]};
    if(l>rq||r<lq)return {0,-1};
    int md = (l+r)/2;
    pair<long long,double> p1 = query(p*2,l,md,lq,rq);
    pair<long long,double> p2 = query(p*2+1,md+1,r,lq,rq);
    if(p1.second>p2.second)return p1;
    else return p2;
}
int n;
vector<long long> x,y;
long long init(int N,int X[],int Y[]){
    n = N;
    for(int i = 0;i<=2e6;i++){
        seg[i] = 1, lazy[i] = 1;
        seg2[i] = 0 , lazy2[i] = 0;
    }
    for(int i = 0;i<n;i++){
        x.push_back(X[i]);
        y.push_back(Y[i]);
        update(1,1,n,i+1,n,X[i],log(X[i]));
        update(1,1,n,i+1,i+1,Y[i],log(Y[i]));
    }
    return query(1,1,n,1,n).first;
}long long updateX(int pos,int val){
     update(1,1,n,pos+1,n,fast(x[pos],mod-2),-log(x[pos]));
     x[pos] = val;
     update(1,1,n,pos+1,n,x[pos],log(x[pos]));
     return query(1,1,n,1,n).first;
}long long updateY(int pos,int val){
     update(1,1,n,pos+1,pos+1,fast(y[pos],mod-2),-log(y[pos]));
     y[pos] = val;
     update(1,1,n,pos+1,pos+1,y[pos],log(y[pos]));
     return query(1,1,n,1,n).first;
}/*
int main(){
    int X[] = {2,1,3};
    int Y[] = {3,4,1};
    cout<<init(3,X,Y)<<endl;
    cout<<updateX(0,1)<<endl;
}*/

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 62796 KB Output is correct
2 Correct 26 ms 62840 KB Output is correct
3 Correct 25 ms 62816 KB Output is correct
4 Correct 22 ms 62932 KB Output is correct
5 Correct 24 ms 62904 KB Output is correct
6 Correct 22 ms 62932 KB Output is correct
7 Correct 22 ms 62804 KB Output is correct
8 Correct 23 ms 62812 KB Output is correct
9 Correct 22 ms 62804 KB Output is correct
10 Correct 21 ms 62884 KB Output is correct
11 Correct 21 ms 62844 KB Output is correct
12 Correct 22 ms 62804 KB Output is correct
13 Correct 22 ms 62804 KB Output is correct
14 Correct 22 ms 62932 KB Output is correct
15 Correct 26 ms 62884 KB Output is correct
16 Correct 22 ms 62796 KB Output is correct
17 Correct 22 ms 62836 KB Output is correct
18 Correct 21 ms 62820 KB Output is correct
19 Correct 22 ms 62880 KB Output is correct
20 Correct 21 ms 62808 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 62920 KB Output is correct
2 Correct 21 ms 62924 KB Output is correct
3 Correct 24 ms 62924 KB Output is correct
4 Correct 22 ms 62848 KB Output is correct
5 Correct 23 ms 62812 KB Output is correct
6 Correct 28 ms 62796 KB Output is correct
7 Correct 27 ms 62876 KB Output is correct
8 Correct 22 ms 62808 KB Output is correct
9 Correct 21 ms 62932 KB Output is correct
10 Correct 21 ms 62876 KB Output is correct
11 Correct 21 ms 62812 KB Output is correct
12 Correct 21 ms 62908 KB Output is correct
13 Correct 21 ms 62812 KB Output is correct
14 Correct 22 ms 62908 KB Output is correct
15 Correct 22 ms 62840 KB Output is correct
16 Correct 22 ms 62804 KB Output is correct
17 Correct 21 ms 62912 KB Output is correct
18 Correct 22 ms 62804 KB Output is correct
19 Correct 21 ms 62796 KB Output is correct
20 Correct 23 ms 62800 KB Output is correct
21 Correct 22 ms 62908 KB Output is correct
22 Correct 22 ms 62804 KB Output is correct
23 Correct 24 ms 62936 KB Output is correct
24 Correct 24 ms 62932 KB Output is correct
25 Correct 26 ms 62916 KB Output is correct
26 Correct 25 ms 62932 KB Output is correct
27 Correct 25 ms 62896 KB Output is correct
28 Correct 24 ms 62820 KB Output is correct
29 Correct 24 ms 62856 KB Output is correct
30 Correct 24 ms 62932 KB Output is correct
31 Correct 24 ms 62864 KB Output is correct
32 Correct 23 ms 62936 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 783 ms 75888 KB Output is correct
2 Correct 966 ms 88468 KB Output is correct
3 Correct 865 ms 79600 KB Output is correct
4 Correct 900 ms 83432 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 62932 KB Output is correct
2 Correct 21 ms 62848 KB Output is correct
3 Correct 22 ms 62892 KB Output is correct
4 Correct 23 ms 62868 KB Output is correct
5 Correct 22 ms 62848 KB Output is correct
6 Correct 21 ms 62924 KB Output is correct
7 Correct 23 ms 62880 KB Output is correct
8 Correct 23 ms 62804 KB Output is correct
9 Correct 23 ms 62844 KB Output is correct
10 Correct 21 ms 62892 KB Output is correct
11 Correct 22 ms 62904 KB Output is correct
12 Correct 22 ms 62804 KB Output is correct
13 Correct 22 ms 62924 KB Output is correct
14 Correct 22 ms 62820 KB Output is correct
15 Correct 21 ms 62888 KB Output is correct
16 Correct 25 ms 62872 KB Output is correct
17 Correct 21 ms 62908 KB Output is correct
18 Correct 21 ms 62844 KB Output is correct
19 Correct 22 ms 62928 KB Output is correct
20 Correct 23 ms 62852 KB Output is correct
21 Correct 23 ms 62804 KB Output is correct
22 Correct 26 ms 62900 KB Output is correct
23 Correct 24 ms 62848 KB Output is correct
24 Correct 29 ms 62932 KB Output is correct
25 Correct 24 ms 62932 KB Output is correct
26 Correct 24 ms 62940 KB Output is correct
27 Correct 24 ms 62944 KB Output is correct
28 Correct 23 ms 62932 KB Output is correct
29 Correct 25 ms 62876 KB Output is correct
30 Correct 27 ms 62908 KB Output is correct
31 Correct 24 ms 62944 KB Output is correct
32 Correct 24 ms 62932 KB Output is correct
33 Correct 650 ms 74916 KB Output is correct
34 Correct 649 ms 78820 KB Output is correct
35 Correct 722 ms 85860 KB Output is correct
36 Correct 725 ms 85804 KB Output is correct
37 Correct 630 ms 77028 KB Output is correct
38 Correct 651 ms 77896 KB Output is correct
39 Correct 626 ms 77064 KB Output is correct
40 Correct 719 ms 80780 KB Output is correct
41 Correct 644 ms 77056 KB Output is correct
42 Correct 629 ms 76964 KB Output is correct
43 Correct 689 ms 81196 KB Output is correct
44 Incorrect 684 ms 81184 KB Output isn't correct
45 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 62804 KB Output is correct
2 Correct 21 ms 62844 KB Output is correct
3 Correct 21 ms 62896 KB Output is correct
4 Correct 21 ms 62876 KB Output is correct
5 Correct 22 ms 62876 KB Output is correct
6 Correct 21 ms 62828 KB Output is correct
7 Correct 20 ms 62932 KB Output is correct
8 Correct 23 ms 62804 KB Output is correct
9 Correct 24 ms 62892 KB Output is correct
10 Correct 22 ms 62896 KB Output is correct
11 Correct 22 ms 62804 KB Output is correct
12 Correct 22 ms 62804 KB Output is correct
13 Correct 24 ms 62832 KB Output is correct
14 Correct 23 ms 62896 KB Output is correct
15 Correct 22 ms 62844 KB Output is correct
16 Correct 22 ms 62824 KB Output is correct
17 Correct 22 ms 62820 KB Output is correct
18 Correct 22 ms 62892 KB Output is correct
19 Correct 22 ms 62828 KB Output is correct
20 Correct 23 ms 62792 KB Output is correct
21 Correct 22 ms 62804 KB Output is correct
22 Correct 21 ms 62896 KB Output is correct
23 Correct 24 ms 62956 KB Output is correct
24 Correct 24 ms 62948 KB Output is correct
25 Correct 26 ms 62940 KB Output is correct
26 Correct 25 ms 62920 KB Output is correct
27 Correct 24 ms 62940 KB Output is correct
28 Correct 24 ms 62924 KB Output is correct
29 Correct 24 ms 62928 KB Output is correct
30 Correct 24 ms 62948 KB Output is correct
31 Correct 23 ms 62932 KB Output is correct
32 Correct 23 ms 62932 KB Output is correct
33 Correct 817 ms 75800 KB Output is correct
34 Correct 964 ms 88520 KB Output is correct
35 Correct 856 ms 79624 KB Output is correct
36 Correct 924 ms 83448 KB Output is correct
37 Correct 660 ms 78888 KB Output is correct
38 Correct 653 ms 78856 KB Output is correct
39 Correct 734 ms 85796 KB Output is correct
40 Correct 720 ms 85760 KB Output is correct
41 Correct 634 ms 77040 KB Output is correct
42 Correct 637 ms 77872 KB Output is correct
43 Correct 627 ms 76924 KB Output is correct
44 Correct 704 ms 80824 KB Output is correct
45 Correct 629 ms 76984 KB Output is correct
46 Correct 628 ms 77024 KB Output is correct
47 Correct 709 ms 81212 KB Output is correct
48 Incorrect 703 ms 81228 KB Output isn't correct
49 Halted 0 ms 0 KB -