oj.uz

Submission #541228

# Submission time Handle Problem Language Result Execution time Memory
541228 2022-03-22T19:35:30 Z new_acc Horses (IOI15_horses) C++14
100 / 100
 193 ms 58560 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef unsigned long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=5e5+10;
const ll mod=1e9+7;
const int SS=1<<19;
struct item{
    ll ilo,ilp,ilk;
    int w;
};
pair<ll,ll>t[N];
item seg[(SS<<1)+10];
item comb(item a,item b){
    item res;
    res.ilo=(a.ilo*b.ilo)%mod;
    if(b.ilp==LLONG_MAX){
        res.ilp=LLONG_MAX;
        res.ilk=b.ilk;
        res.w=b.w;
    }else{
        if(t[a.w].se<a.ilk*b.ilp or t[a.w].se<a.ilk*b.ilp*t[b.w].se){
            res.w=b.w;
            res.ilk=b.ilk;
            if(a.ilp>(ll)1e9 or b.ilp*a.ilk>(ll)1e9) res.ilp=LLONG_MAX;
            else res.ilp=a.ilp*a.ilk*b.ilp;
        }else{
            res.w=a.w;
            res.ilp=a.ilp;
            res.ilk=a.ilk*b.ilp*b.ilk;
        }
    }
    if(res.ilp>(ll)1e9) res.ilp=LLONG_MAX;
    return res;
}
void upd(int ind){
    ind+=SS;
    seg[ind].w=ind-SS,seg[ind].ilo=t[ind-SS].fi;
    seg[ind].ilp=t[ind-SS].fi,seg[ind].ilk=1;
    for(ind>>=1;ind>0;ind>>=1) seg[ind]=comb(seg[ind<<1],seg[(ind<<1)+1]);
}
int Query(int a,int b){
    ll res=1;
    for(a+=SS-1,b+=SS+1;(a>>1)!=(b>>1);a>>=1,b>>=1){
        if(!(a&1)) (res*=seg[a+1].ilo)%=mod;
        if(b&1) (res*=seg[b-1].ilo)%=mod;
    }
    return res;
}
int init(int n,int x[],int y[]){
    for(int i=0;i<n;i++) t[i+1]={x[i],y[i]};
    for(int ind=1;ind<=(SS<<1);ind++) seg[ind].ilo=1,seg[ind].ilp=1,seg[ind].ilk=1;
    for(int i=1;i<=n;i++) upd(i);
    return (Query(1,seg[1].w)*t[seg[1].w].se)%mod;
}
int updateX(int pos,int val){
    pos++;
    t[pos].fi=val;
    upd(pos);
    return (Query(1,seg[1].w)*t[seg[1].w].se)%mod;
}
int updateY(int pos,int val){
    pos++;
    t[pos].se=val;
    upd(pos);
    return (Query(1,seg[1].w)*t[seg[1].w].se)%mod;
}

Compilation message

horses.cpp: In function 'int Query(int, int)':
horses.cpp:52:12: warning: conversion from 'll' {aka 'long long unsigned int'} to 'int' may change value [-Wconversion]
   52 |     return res;
      |            ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:58:46: warning: conversion from 'long long unsigned int' to 'int' may change value [-Wconversion]
   58 |     return (Query(1,seg[1].w)*t[seg[1].w].se)%mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:64:46: warning: conversion from 'long long unsigned int' to 'int' may change value [-Wconversion]
   64 |     return (Query(1,seg[1].w)*t[seg[1].w].se)%mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:70:46: warning: conversion from 'long long unsigned int' to 'int' may change value [-Wconversion]
   70 |     return (Query(1,seg[1].w)*t[seg[1].w].se)%mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33108 KB Output is correct
2 Correct 15 ms 33060 KB Output is correct
3 Correct 14 ms 33020 KB Output is correct
4 Correct 15 ms 33108 KB Output is correct
5 Correct 15 ms 33108 KB Output is correct
6 Correct 15 ms 33048 KB Output is correct
7 Correct 14 ms 33108 KB Output is correct
8 Correct 14 ms 33108 KB Output is correct
9 Correct 13 ms 33108 KB Output is correct
10 Correct 17 ms 33040 KB Output is correct
11 Correct 14 ms 33060 KB Output is correct
12 Correct 15 ms 33100 KB Output is correct
13 Correct 14 ms 33108 KB Output is correct
14 Correct 14 ms 33076 KB Output is correct
15 Correct 14 ms 33144 KB Output is correct
16 Correct 15 ms 33092 KB Output is correct
17 Correct 15 ms 33108 KB Output is correct
18 Correct 17 ms 33092 KB Output is correct
19 Correct 15 ms 33108 KB Output is correct
20 Correct 16 ms 33108 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33108 KB Output is correct
2 Correct 15 ms 33108 KB Output is correct
3 Correct 14 ms 33108 KB Output is correct
4 Correct 14 ms 33108 KB Output is correct
5 Correct 15 ms 33056 KB Output is correct
6 Correct 13 ms 33108 KB Output is correct
7 Correct 18 ms 33108 KB Output is correct
8 Correct 15 ms 33032 KB Output is correct
9 Correct 14 ms 33108 KB Output is correct
10 Correct 14 ms 33108 KB Output is correct
11 Correct 15 ms 33108 KB Output is correct
12 Correct 14 ms 33108 KB Output is correct
13 Correct 14 ms 33108 KB Output is correct
14 Correct 15 ms 33108 KB Output is correct
15 Correct 14 ms 33108 KB Output is correct
16 Correct 13 ms 33108 KB Output is correct
17 Correct 14 ms 33144 KB Output is correct
18 Correct 16 ms 33092 KB Output is correct
19 Correct 15 ms 33148 KB Output is correct
20 Correct 14 ms 33108 KB Output is correct
21 Correct 14 ms 33108 KB Output is correct
22 Correct 15 ms 33108 KB Output is correct
23 Correct 18 ms 33140 KB Output is correct
24 Correct 16 ms 33108 KB Output is correct
25 Correct 15 ms 33236 KB Output is correct
26 Correct 15 ms 33104 KB Output is correct
27 Correct 15 ms 33180 KB Output is correct
28 Correct 14 ms 33176 KB Output is correct
29 Correct 17 ms 33216 KB Output is correct
30 Correct 15 ms 33108 KB Output is correct
31 Correct 16 ms 33080 KB Output is correct
32 Correct 14 ms 33128 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 45784 KB Output is correct
2 Correct 188 ms 58396 KB Output is correct
3 Correct 167 ms 49664 KB Output is correct
4 Correct 174 ms 53460 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33108 KB Output is correct
2 Correct 14 ms 33056 KB Output is correct
3 Correct 14 ms 33108 KB Output is correct
4 Correct 15 ms 33108 KB Output is correct
5 Correct 15 ms 33236 KB Output is correct
6 Correct 15 ms 33048 KB Output is correct
7 Correct 16 ms 33092 KB Output is correct
8 Correct 15 ms 33100 KB Output is correct
9 Correct 19 ms 33108 KB Output is correct
10 Correct 14 ms 33108 KB Output is correct
11 Correct 14 ms 33136 KB Output is correct
12 Correct 14 ms 33108 KB Output is correct
13 Correct 14 ms 33088 KB Output is correct
14 Correct 14 ms 33108 KB Output is correct
15 Correct 15 ms 33052 KB Output is correct
16 Correct 15 ms 33180 KB Output is correct
17 Correct 15 ms 33088 KB Output is correct
18 Correct 16 ms 33108 KB Output is correct
19 Correct 17 ms 33108 KB Output is correct
20 Correct 14 ms 33108 KB Output is correct
21 Correct 14 ms 33092 KB Output is correct
22 Correct 15 ms 33120 KB Output is correct
23 Correct 14 ms 33152 KB Output is correct
24 Correct 14 ms 33204 KB Output is correct
25 Correct 14 ms 33108 KB Output is correct
26 Correct 14 ms 33108 KB Output is correct
27 Correct 14 ms 33124 KB Output is correct
28 Correct 17 ms 33092 KB Output is correct
29 Correct 14 ms 33088 KB Output is correct
30 Correct 16 ms 33108 KB Output is correct
31 Correct 16 ms 33088 KB Output is correct
32 Correct 15 ms 33068 KB Output is correct
33 Correct 104 ms 48784 KB Output is correct
34 Correct 106 ms 48844 KB Output is correct
35 Correct 146 ms 55796 KB Output is correct
36 Correct 133 ms 55756 KB Output is correct
37 Correct 93 ms 46980 KB Output is correct
38 Correct 109 ms 47888 KB Output is correct
39 Correct 87 ms 46856 KB Output is correct
40 Correct 116 ms 50792 KB Output is correct
41 Correct 93 ms 46892 KB Output is correct
42 Correct 90 ms 46964 KB Output is correct
43 Correct 111 ms 51256 KB Output is correct
44 Correct 116 ms 51200 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33108 KB Output is correct
2 Correct 13 ms 33108 KB Output is correct
3 Correct 14 ms 33108 KB Output is correct
4 Correct 15 ms 33104 KB Output is correct
5 Correct 14 ms 33108 KB Output is correct
6 Correct 12 ms 33108 KB Output is correct
7 Correct 14 ms 33132 KB Output is correct
8 Correct 14 ms 33108 KB Output is correct
9 Correct 13 ms 33080 KB Output is correct
10 Correct 14 ms 33076 KB Output is correct
11 Correct 13 ms 33124 KB Output is correct
12 Correct 15 ms 33108 KB Output is correct
13 Correct 14 ms 33088 KB Output is correct
14 Correct 13 ms 33108 KB Output is correct
15 Correct 15 ms 33108 KB Output is correct
16 Correct 13 ms 33108 KB Output is correct
17 Correct 13 ms 33044 KB Output is correct
18 Correct 14 ms 33028 KB Output is correct
19 Correct 13 ms 33144 KB Output is correct
20 Correct 13 ms 33108 KB Output is correct
21 Correct 13 ms 33108 KB Output is correct
22 Correct 14 ms 33152 KB Output is correct
23 Correct 14 ms 33092 KB Output is correct
24 Correct 17 ms 33064 KB Output is correct
25 Correct 14 ms 33108 KB Output is correct
26 Correct 14 ms 33108 KB Output is correct
27 Correct 15 ms 33108 KB Output is correct
28 Correct 14 ms 33108 KB Output is correct
29 Correct 13 ms 33084 KB Output is correct
30 Correct 13 ms 33108 KB Output is correct
31 Correct 13 ms 33084 KB Output is correct
32 Correct 13 ms 33076 KB Output is correct
33 Correct 135 ms 49596 KB Output is correct
34 Correct 193 ms 58560 KB Output is correct
35 Correct 156 ms 49552 KB Output is correct
36 Correct 171 ms 53412 KB Output is correct
37 Correct 109 ms 48892 KB Output is correct
38 Correct 106 ms 48896 KB Output is correct
39 Correct 145 ms 55856 KB Output is correct
40 Correct 148 ms 55704 KB Output is correct
41 Correct 100 ms 46980 KB Output is correct
42 Correct 117 ms 47888 KB Output is correct
43 Correct 108 ms 46860 KB Output is correct
44 Correct 128 ms 50788 KB Output is correct
45 Correct 105 ms 46928 KB Output is correct
46 Correct 91 ms 47008 KB Output is correct
47 Correct 122 ms 51260 KB Output is correct
48 Correct 111 ms 51232 KB Output is correct
49 Correct 181 ms 50904 KB Output is correct
50 Correct 184 ms 50872 KB Output is correct
51 Correct 171 ms 57676 KB Output is correct
52 Correct 170 ms 57164 KB Output is correct
53 Correct 174 ms 49340 KB Output is correct
54 Correct 173 ms 49784 KB Output is correct
55 Correct 147 ms 47996 KB Output is correct
56 Correct 177 ms 52584 KB Output is correct
57 Correct 129 ms 48632 KB Output is correct
58 Correct 135 ms 49084 KB Output is correct
59 Correct 125 ms 51152 KB Output is correct