oj.uz

Submission #330952

# Submission time Handle Problem Language Result Execution time Memory
330952 2020-11-27T00:44:02 Z monkey8 Horses (IOI15_horses) C++17
100 / 100
 1056 ms 62316 KB 
#include "horses.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cstdio>
#include <utility> 
#include <queue>
#include <math.h>
#include <set>
#include <bitset>
#include <cmath>
#include <bitset>
#include <iterator>
#include <limits>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, int> pdi;
typedef unsigned long long ull;
typedef __uint128_t L;
const ll MOD = 1e9 + 7;
const int MAXN = 500010;
pdi st[MAXN << 2];
double lazy[MAXN << 2];
ll st1[MAXN << 2];
ll lazy1[MAXN << 2];
int xval[MAXN];
int yval[MAXN];
struct FastMod {
    ull b, m;
    FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
    ull reduce(ull a) {
        ull q = (ull)((L(m) * a) >> 64);
        ull r = a - q * b;
        return r >= b ? r - b : r;
    }
};
FastMod F(2);
int left(int p) {
    return (p << 1);
}
int right(int p) {
    return (p << 1) + 1;
}
void build(int p, int L, int R) {
    if(L == R) st[p] = pdi(log2(yval[L]), L);
    else {
        build(left(p), L, (L + R)/2);
        build(right(p), (L + R)/2 + 1, R);
        st[p] = max(st[left(p)], st[right(p)]);
    }
}
void push(int p, int L, int R) {
    st[p].first += lazy[p];
    if(L != R) {
        lazy[left(p)] += lazy[p];
        lazy[right(p)] += lazy[p];
    }
    lazy[p] = 0;
}
void update(int p, int L, int R, int i, int j, double val) {
    push(p, L, R);
    if(i > R || j < L) return;
    if(L >= i && R <= j) {
        lazy[p] += val;
        push(p, L, R);
        return;
    }
    update(left(p), L, (L + R)/2, i, j, val);
    update(right(p), (L + R)/2 + 1, R, i, j, val);
    st[p] = max(st[left(p)], st[right(p)]);
}
pdi query(int p, int L, int R, int i, int j) {
    push(p, L, R);
    if(i > R || j < L) return pdi(-1, -1);
    if(L >= i && R <= j) return st[p];
    return max(query(left(p), L, (L + R)/2, i, j), query(right(p), (L + R)/2 + 1, R, i, j));
}
void build1(int p, int L, int R) {
    lazy1[p] = 1;
    if(L == R) st1[p] = yval[L];
    else {
        build1(left(p), L, (L + R)/2);
        build1(right(p), (L + R)/2 + 1, R);
        st1[p] = max(st1[left(p)], st1[right(p)]);
    }
}
void push1(int p, int L, int R) {
    st1[p] = F.reduce(st1[p] * lazy1[p]);
    if(L != R) {
        lazy1[left(p)] = F.reduce(lazy1[left(p)] * lazy1[p]);
        lazy1[right(p)] = F.reduce(lazy1[right(p)] * lazy1[p]);
    }
    lazy1[p] = 1;
}
void update1(int p, int L, int R, int i, int j, ll val) {
    push1(p, L, R);
    if(i > R || j < L) return;
    if(L >= i && R <= j) {
        lazy1[p] = F.reduce(lazy1[p] * val);
        push1(p, L, R);
        return;
    }
    update1(left(p), L, (L + R)/2, i, j, val);
    update1(right(p), (L + R)/2 + 1, R, i, j, val);
    st1[p] = max(st1[left(p)], st1[right(p)]);
}
ll query1(int p, int L, int R, int i) {
    push1(p, L, R);
    if(L == R && i == L) return st1[p];
    if(i < L || i > R) return 0;
    return max(query1(left(p), L, (L + R)/2, i), query1(right(p), (L + R)/2 + 1, R, i));
}
ll poww(ll x, ll y) {
    if(y == 0) return 1;
    if(y == 1) return x;
    ll z = poww(x, y/2);
    if(y % 2 == 0) return F.reduce(z * z);
    return F.reduce(F.reduce(z * z) * x);
}
int N;
int init(int n, int x[], int y[]) {
    F = FastMod(MOD);
    N = n;
    for(int i = 0; i < n; i++)
        yval[i] = y[i];
    build(1, 0, n - 1);
    build1(1, 0, n - 1);
    for(int i = 0; i < n; i++) {
        xval[i] = x[i];
        update(1, 0, n - 1, i, n - 1, log2(x[i]));
        update1(1, 0, n - 1, i, n - 1, x[i]);
    }
    pdi q = query(1, 0, n - 1, 0, n - 1);
    return query1(1, 0, n - 1, q.second);
}
int updateX(int pos, int val) {
    update(1, 0, N - 1, pos, N - 1, log2(val) - log2(xval[pos]));
    update1(1, 0, N - 1, pos, N - 1, F.reduce((ll)val * poww(xval[pos], MOD - 2)));
    xval[pos] = val;
    pdi q = query(1, 0, N - 1, 0, N - 1);
    return query1(1, 0, N - 1, q.second);
}
int updateY(int pos, int val) {
    update(1, 0, N - 1, pos, pos, log2(val) - log2(yval[pos]));
    update1(1, 0, N - 1, pos, pos, F.reduce((ll)val * poww(yval[pos], MOD - 2)));
    yval[pos] = val;
    pdi q = query(1, 0, N - 1, 0, N - 1);
    return query1(1, 0, N - 1, q.second);
}

Compilation message

horses.cpp: In constructor 'FastMod::FastMod(ull)':
horses.cpp:33:20: warning: declaration of 'b' shadows a member of 'FastMod' [-Wshadow]
   33 |     FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
      |                    ^
horses.cpp:32:9: note: shadowed declaration is here
   32 |     ull b, m;
      |         ^
horses.cpp: In constructor 'FastMod::FastMod(ull)':
horses.cpp:33:54: warning: declaration of 'b' shadows a member of 'FastMod' [-Wshadow]
   33 |     FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
      |                                                      ^
horses.cpp:32:9: note: shadowed declaration is here
   32 |     ull b, m;
      |         ^
horses.cpp: In constructor 'FastMod::FastMod(ull)':
horses.cpp:33:54: warning: declaration of 'b' shadows a member of 'FastMod' [-Wshadow]
   33 |     FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
      |                                                      ^
horses.cpp:32:9: note: shadowed declaration is here
   32 |     ull b, m;
      |         ^
horses.cpp: In function 'void build(int, int, int)':
horses.cpp:47:31: warning: declaration of 'L' shadows a global declaration [-Wshadow]
   47 | void build(int p, int L, int R) {
      |                               ^
horses.cpp:22:21: note: shadowed declaration is here
   22 | typedef __uint128_t L;
      |                     ^
horses.cpp: In function 'void push(int, int, int)':
horses.cpp:55:30: warning: declaration of 'L' shadows a global declaration [-Wshadow]
   55 | void push(int p, int L, int R) {
      |                              ^
horses.cpp:22:21: note: shadowed declaration is here
   22 | typedef __uint128_t L;
      |                     ^
horses.cpp: In function 'void update(int, int, int, int, int, double)':
horses.cpp:63:58: warning: declaration of 'L' shadows a global declaration [-Wshadow]
   63 | void update(int p, int L, int R, int i, int j, double val) {
      |                                                          ^
horses.cpp:22:21: note: shadowed declaration is here
   22 | typedef __uint128_t L;
      |                     ^
horses.cpp: In function 'pdi query(int, int, int, int, int)':
horses.cpp:75:44: warning: declaration of 'L' shadows a global declaration [-Wshadow]
   75 | pdi query(int p, int L, int R, int i, int j) {
      |                                            ^
horses.cpp:22:21: note: shadowed declaration is here
   22 | typedef __uint128_t L;
      |                     ^
horses.cpp: In function 'void build1(int, int, int)':
horses.cpp:81:32: warning: declaration of 'L' shadows a global declaration [-Wshadow]
   81 | void build1(int p, int L, int R) {
      |                                ^
horses.cpp:22:21: note: shadowed declaration is here
   22 | typedef __uint128_t L;
      |                     ^
horses.cpp: In function 'void push1(int, int, int)':
horses.cpp:90:31: warning: declaration of 'L' shadows a global declaration [-Wshadow]
   90 | void push1(int p, int L, int R) {
      |                               ^
horses.cpp:22:21: note: shadowed declaration is here
   22 | typedef __uint128_t L;
      |                     ^
horses.cpp: In function 'void update1(int, int, int, int, int, ll)':
horses.cpp:98:55: warning: declaration of 'L' shadows a global declaration [-Wshadow]
   98 | void update1(int p, int L, int R, int i, int j, ll val) {
      |                                                       ^
horses.cpp:22:21: note: shadowed declaration is here
   22 | typedef __uint128_t L;
      |                     ^
horses.cpp: In function 'll query1(int, int, int, int)':
horses.cpp:110:37: warning: declaration of 'L' shadows a global declaration [-Wshadow]
  110 | ll query1(int p, int L, int R, int i) {
      |                                     ^
horses.cpp:22:21: note: shadowed declaration is here
   22 | typedef __uint128_t L;
      |                     ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:137:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  137 |     return query1(1, 0, n - 1, q.second);
      |            ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:144:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  144 |     return query1(1, 0, N - 1, q.second);
      |            ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:151:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  151 |     return query1(1, 0, N - 1, q.second);
      |            ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 828 ms 50284 KB Output is correct
2 Correct 1041 ms 50360 KB Output is correct
3 Correct 1000 ms 54124 KB Output is correct
4 Correct 1042 ms 57836 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 0 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 3 ms 492 KB Output is correct
24 Correct 3 ms 492 KB Output is correct
25 Correct 3 ms 492 KB Output is correct
26 Correct 3 ms 492 KB Output is correct
27 Correct 3 ms 620 KB Output is correct
28 Correct 3 ms 492 KB Output is correct
29 Correct 2 ms 492 KB Output is correct
30 Correct 3 ms 492 KB Output is correct
31 Correct 2 ms 492 KB Output is correct
32 Correct 3 ms 492 KB Output is correct
33 Correct 683 ms 49388 KB Output is correct
34 Correct 683 ms 49516 KB Output is correct
35 Correct 682 ms 49644 KB Output is correct
36 Correct 688 ms 49772 KB Output is correct
37 Correct 644 ms 49460 KB Output is correct
38 Correct 660 ms 49296 KB Output is correct
39 Correct 632 ms 49260 KB Output is correct
40 Correct 661 ms 49372 KB Output is correct
41 Correct 639 ms 49260 KB Output is correct
42 Correct 634 ms 49388 KB Output is correct
43 Correct 644 ms 49388 KB Output is correct
44 Correct 644 ms 49260 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 0 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 0 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 0 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 3 ms 492 KB Output is correct
24 Correct 3 ms 492 KB Output is correct
25 Correct 3 ms 492 KB Output is correct
26 Correct 3 ms 492 KB Output is correct
27 Correct 3 ms 492 KB Output is correct
28 Correct 3 ms 620 KB Output is correct
29 Correct 2 ms 492 KB Output is correct
30 Correct 3 ms 492 KB Output is correct
31 Correct 3 ms 512 KB Output is correct
32 Correct 3 ms 492 KB Output is correct
33 Correct 820 ms 50284 KB Output is correct
34 Correct 1043 ms 50540 KB Output is correct
35 Correct 982 ms 53996 KB Output is correct
36 Correct 1014 ms 57964 KB Output is correct
37 Correct 689 ms 53484 KB Output is correct
38 Correct 708 ms 53484 KB Output is correct
39 Correct 694 ms 60268 KB Output is correct
40 Correct 688 ms 60384 KB Output is correct
41 Correct 646 ms 51532 KB Output is correct
42 Correct 664 ms 52460 KB Output is correct
43 Correct 626 ms 51308 KB Output is correct
44 Correct 667 ms 55276 KB Output is correct
45 Correct 642 ms 51436 KB Output is correct
46 Correct 630 ms 51436 KB Output is correct
47 Correct 647 ms 55788 KB Output is correct
48 Correct 640 ms 55660 KB Output is correct
49 Correct 1056 ms 55532 KB Output is correct
50 Correct 1028 ms 55404 KB Output is correct
51 Correct 887 ms 62316 KB Output is correct
52 Correct 875 ms 61768 KB Output is correct
53 Correct 991 ms 53740 KB Output is correct
54 Correct 872 ms 54380 KB Output is correct
55 Correct 820 ms 52460 KB Output is correct
56 Correct 882 ms 57196 KB Output is correct
57 Correct 820 ms 53064 KB Output is correct
58 Correct 831 ms 53612 KB Output is correct
59 Correct 644 ms 55788 KB Output is correct