oj.uz

Submission #670098

# Submission time Handle Problem Language Result Execution time Memory
670098 2022-12-08T06:19:56 Z Astrayt Horses (IOI15_horses) C++17
100 / 100
 733 ms 126168 KB 
#include <bits/stdc++.h>
using namespace std;
#define starburst ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//#define int long long
#define double long double
#define pii pair<int,int>
#define pb push_back
#define maxn 500005
#define mod 1000000007ll
#define ff first
#define ss second

int N;
vector<int> X, Y;
vector<double> lgX, lgY, PlgX;

int fastpow(int a, int b){
    int ret = 1;
    for(; b; b >>= 1){
        if(b & 1) ret = 1ll * ret * a % mod;
        a = 1ll * a * a % mod;
    }
    return ret;
}

struct FenwickTree{
    int val[maxn];
    void init(int n){
        for(int i = 0; i <= n; ++i) val[i] = 1;
    }
    void modify(int p, int x){
        for(; p < maxn; p += (p & -p)) val[p] = 1ll * x * val[p] % mod;
    }
    int query(int p){
        int ret = 1;
        for(; p; p -= (p & -p)){
            ret = 1ll * ret * val[p] % mod;
        }
        return ret;
    }
}bit;

struct SegmentTree{
    pair<double, int> node[4 * maxn];
    double tag[4 * maxn];
    void push(int i){
        double t = tag[i];
        node[2 * i].ff += t, tag[2 * i] += t;
        node[2 * i + 1].ff += t, tag[2 * i + 1] += t;
        tag[i] = 0;
        node[i] = max(node[2 * i], node[2 * i + 1]);
    }
    void modify(int i, int l, int r, int ql, int qr, double x){
        if(l == r){
            node[i].ff += x;
            node[i].ss = l;
            return;
        }
        push(i);
        if(ql <= l && r <= qr){
            node[i].ff += x;
            tag[i] += x;
            return;
        }
        int mid = (l + r) / 2;
        if(ql <= mid) modify(2 * i, l, mid, ql, qr, x);
        if(mid < qr) modify(2 * i + 1, mid + 1, r, ql, qr, x);
        node[i] = max(node[2 * i], node[2 * i + 1]);
    }
}seg;

int init(int n, int *x, int *y){
    N = n;
    bit.init(N + 1);
    X.assign(N + 1, 0), Y.assign(N + 1, 0);
    lgX.assign(N + 1, 0.0), lgY.assign(N + 1, 0.0), PlgX.assign(N + 1, 0.0);
    for(int i = 1; i <= n; ++i){
        X[i] = x[i - 1], Y[i] = y[i - 1];
        lgX[i] = log(X[i]), lgY[i] = log(Y[i]);
        PlgX[i] = PlgX[i - 1] + lgX[i];
        bit.modify(i, X[i]);
        seg.modify(1, 1, N, i, i, PlgX[i] + lgY[i]);
    }
    int id = seg.node[1].ss;
    int BX = bit.query(id);
    return 1ll * BX * Y[id] % mod;
}

int updateX(int pos, int val){
    pos++;
    bit.modify(pos, fastpow(X[pos], mod - 2));
    bit.modify(pos, val);
    seg.modify(1, 1, N, pos, N, -lgX[pos]);
    X[pos] = val;
    lgX[pos] = log(val);
    seg.modify(1, 1, N, pos, N, lgX[pos]);
    int id = seg.node[1].ss;
    int BX = bit.query(id);
    return 1ll * BX * Y[id] % mod;
}

int updateY(int pos, int val){
    pos++;
    seg.modify(1, 1, N, pos, pos, -lgY[pos]);
    Y[pos] = val;
    lgY[pos] = log(val);
    seg.modify(1, 1, N, pos, pos, lgY[pos]);
    int id = seg.node[1].ss;
    int BX = bit.query(id);
    return 1ll * BX * Y[id] % mod;
}

Compilation message

horses.cpp: In function 'int fastpow(int, int)':
horses.cpp:20:39: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   20 |         if(b & 1) ret = 1ll * ret * a % mod;
      |                                       ^
horses.cpp:21:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   21 |         a = 1ll * a * a % mod;
      |                         ^
horses.cpp: In member function 'void FenwickTree::modify(int, int)':
horses.cpp:32:66: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   32 |         for(; p < maxn; p += (p & -p)) val[p] = 1ll * x * val[p] % mod;
      |                                                                  ^
horses.cpp: In member function 'int FenwickTree::query(int)':
horses.cpp:37:38: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   37 |             ret = 1ll * ret * val[p] % mod;
      |                                      ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:86:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   86 |     return 1ll * BX * Y[id] % mod;
      |                             ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:99:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   99 |     return 1ll * BX * Y[id] % mod;
      |                             ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:110:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  110 |     return 1ll * BX * Y[id] % mod;
      |                             ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 62932 KB Output is correct
2 Correct 26 ms 62932 KB Output is correct
3 Correct 25 ms 62932 KB Output is correct
4 Correct 25 ms 62860 KB Output is correct
5 Correct 25 ms 62916 KB Output is correct
6 Correct 25 ms 62896 KB Output is correct
7 Correct 25 ms 62932 KB Output is correct
8 Correct 26 ms 62932 KB Output is correct
9 Correct 24 ms 62872 KB Output is correct
10 Correct 25 ms 62932 KB Output is correct
11 Correct 25 ms 62972 KB Output is correct
12 Correct 26 ms 62932 KB Output is correct
13 Correct 27 ms 62940 KB Output is correct
14 Correct 27 ms 63052 KB Output is correct
15 Correct 25 ms 62924 KB Output is correct
16 Correct 26 ms 62872 KB Output is correct
17 Correct 25 ms 62880 KB Output is correct
18 Correct 25 ms 62872 KB Output is correct
19 Correct 26 ms 62932 KB Output is correct
20 Correct 25 ms 62964 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 62932 KB Output is correct
2 Correct 25 ms 62952 KB Output is correct
3 Correct 25 ms 62932 KB Output is correct
4 Correct 25 ms 62892 KB Output is correct
5 Correct 32 ms 62908 KB Output is correct
6 Correct 25 ms 62872 KB Output is correct
7 Correct 26 ms 62892 KB Output is correct
8 Correct 25 ms 62932 KB Output is correct
9 Correct 25 ms 62876 KB Output is correct
10 Correct 25 ms 62968 KB Output is correct
11 Correct 25 ms 62964 KB Output is correct
12 Correct 26 ms 62912 KB Output is correct
13 Correct 29 ms 62912 KB Output is correct
14 Correct 25 ms 62892 KB Output is correct
15 Correct 25 ms 62932 KB Output is correct
16 Correct 25 ms 62924 KB Output is correct
17 Correct 25 ms 62964 KB Output is correct
18 Correct 28 ms 62944 KB Output is correct
19 Correct 26 ms 62908 KB Output is correct
20 Correct 25 ms 62952 KB Output is correct
21 Correct 26 ms 62912 KB Output is correct
22 Correct 25 ms 62904 KB Output is correct
23 Correct 26 ms 63032 KB Output is correct
24 Correct 27 ms 63056 KB Output is correct
25 Correct 28 ms 63020 KB Output is correct
26 Correct 27 ms 63088 KB Output is correct
27 Correct 26 ms 63000 KB Output is correct
28 Correct 27 ms 63020 KB Output is correct
29 Correct 27 ms 63028 KB Output is correct
30 Correct 27 ms 63052 KB Output is correct
31 Correct 26 ms 63052 KB Output is correct
32 Correct 28 ms 63052 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 113572 KB Output is correct
2 Correct 685 ms 126092 KB Output is correct
3 Correct 647 ms 117368 KB Output is correct
4 Correct 698 ms 121264 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 62932 KB Output is correct
2 Correct 24 ms 62932 KB Output is correct
3 Correct 23 ms 62956 KB Output is correct
4 Correct 27 ms 62932 KB Output is correct
5 Correct 24 ms 62968 KB Output is correct
6 Correct 25 ms 62956 KB Output is correct
7 Correct 25 ms 62932 KB Output is correct
8 Correct 24 ms 62868 KB Output is correct
9 Correct 24 ms 62952 KB Output is correct
10 Correct 24 ms 62932 KB Output is correct
11 Correct 25 ms 62968 KB Output is correct
12 Correct 24 ms 62932 KB Output is correct
13 Correct 25 ms 62920 KB Output is correct
14 Correct 26 ms 62916 KB Output is correct
15 Correct 25 ms 62908 KB Output is correct
16 Correct 25 ms 62972 KB Output is correct
17 Correct 25 ms 62932 KB Output is correct
18 Correct 25 ms 62932 KB Output is correct
19 Correct 25 ms 62920 KB Output is correct
20 Correct 29 ms 62916 KB Output is correct
21 Correct 25 ms 62852 KB Output is correct
22 Correct 26 ms 62876 KB Output is correct
23 Correct 28 ms 63296 KB Output is correct
24 Correct 27 ms 63100 KB Output is correct
25 Correct 29 ms 63036 KB Output is correct
26 Correct 27 ms 63008 KB Output is correct
27 Correct 26 ms 63060 KB Output is correct
28 Correct 26 ms 63060 KB Output is correct
29 Correct 27 ms 62996 KB Output is correct
30 Correct 29 ms 63204 KB Output is correct
31 Correct 26 ms 63060 KB Output is correct
32 Correct 26 ms 63060 KB Output is correct
33 Correct 410 ms 116700 KB Output is correct
34 Correct 416 ms 116592 KB Output is correct
35 Correct 420 ms 123472 KB Output is correct
36 Correct 441 ms 123640 KB Output is correct
37 Correct 406 ms 114820 KB Output is correct
38 Correct 407 ms 115616 KB Output is correct
39 Correct 389 ms 114696 KB Output is correct
40 Correct 421 ms 118544 KB Output is correct
41 Correct 387 ms 114764 KB Output is correct
42 Correct 393 ms 114784 KB Output is correct
43 Correct 395 ms 119020 KB Output is correct
44 Correct 391 ms 118988 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 62932 KB Output is correct
2 Correct 27 ms 62860 KB Output is correct
3 Correct 25 ms 62908 KB Output is correct
4 Correct 25 ms 62928 KB Output is correct
5 Correct 25 ms 62876 KB Output is correct
6 Correct 25 ms 62940 KB Output is correct
7 Correct 25 ms 62872 KB Output is correct
8 Correct 25 ms 62968 KB Output is correct
9 Correct 27 ms 62968 KB Output is correct
10 Correct 26 ms 62976 KB Output is correct
11 Correct 26 ms 62924 KB Output is correct
12 Correct 27 ms 62932 KB Output is correct
13 Correct 25 ms 62936 KB Output is correct
14 Correct 27 ms 62892 KB Output is correct
15 Correct 30 ms 62900 KB Output is correct
16 Correct 26 ms 62932 KB Output is correct
17 Correct 27 ms 62860 KB Output is correct
18 Correct 25 ms 62884 KB Output is correct
19 Correct 27 ms 62976 KB Output is correct
20 Correct 26 ms 62932 KB Output is correct
21 Correct 26 ms 62868 KB Output is correct
22 Correct 25 ms 62900 KB Output is correct
23 Correct 29 ms 63052 KB Output is correct
24 Correct 29 ms 63088 KB Output is correct
25 Correct 27 ms 63064 KB Output is correct
26 Correct 27 ms 63048 KB Output is correct
27 Correct 26 ms 63036 KB Output is correct
28 Correct 28 ms 63056 KB Output is correct
29 Correct 27 ms 63064 KB Output is correct
30 Correct 32 ms 63056 KB Output is correct
31 Correct 27 ms 63076 KB Output is correct
32 Correct 28 ms 63052 KB Output is correct
33 Correct 509 ms 117460 KB Output is correct
34 Correct 686 ms 126168 KB Output is correct
35 Correct 692 ms 117476 KB Output is correct
36 Correct 733 ms 121252 KB Output is correct
37 Correct 409 ms 116556 KB Output is correct
38 Correct 424 ms 116680 KB Output is correct
39 Correct 418 ms 123528 KB Output is correct
40 Correct 432 ms 123528 KB Output is correct
41 Correct 408 ms 114908 KB Output is correct
42 Correct 407 ms 115652 KB Output is correct
43 Correct 394 ms 114692 KB Output is correct
44 Correct 408 ms 118604 KB Output is correct
45 Correct 394 ms 114816 KB Output is correct
46 Correct 376 ms 114864 KB Output is correct
47 Correct 402 ms 118980 KB Output is correct
48 Correct 403 ms 119000 KB Output is correct
49 Correct 664 ms 118700 KB Output is correct
50 Correct 675 ms 118592 KB Output is correct
51 Correct 561 ms 125384 KB Output is correct
52 Correct 594 ms 124904 KB Output is correct
53 Correct 700 ms 116932 KB Output is correct
54 Correct 575 ms 117520 KB Output is correct
55 Correct 552 ms 115712 KB Output is correct
56 Correct 588 ms 120452 KB Output is correct
57 Correct 516 ms 116372 KB Output is correct
58 Correct 527 ms 116804 KB Output is correct
59 Correct 397 ms 118984 KB Output is correct