oj.uz

Submission #1088254

# Submission time Handle Problem Language Result Execution time Memory
1088254 2024-09-14T07:18:27 Z yeediot Horses (IOI15_horses) C++17
100 / 100
 114 ms 54608 KB 
#include<bits/stdc++.h>
#include "horses.h"
using namespace std;
#define ll long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define __lg(x) 63-__builtin_clzll(x)
#define pow2(x) (1LL<<x)
const int mxn = 5e5 + 5, mod = 1e9 + 7;
int x[mxn], y[mxn], n;
struct segtree{
    struct node{
        ll mx, sum;
        double lmx, lsum;
    }seg[4 * mxn];
    void merge(int id){
        seg[id].sum = seg[id * 2].sum * seg[id * 2 + 1].sum % mod;
        double L = seg[id * 2].lmx, R = seg[id * 2].lsum + seg[id * 2 + 1].lmx;
        if(R > L){
            seg[id].mx = seg[id * 2 + 1].mx * seg[id * 2].sum % mod;
            seg[id].lmx = R;
        }
        else{
            seg[id].mx = seg[id * 2].mx;
            seg[id].lmx = L;
        }
        seg[id].lsum = seg[id * 2].lsum + seg[id * 2 + 1].lsum;
    }
    void build(int l, int r, int id){
        if(l == r){
            seg[id].mx = (ll)x[l] * y[l] % mod;
            seg[id].sum = x[l];
            seg[id].lmx = log2((ll)x[l] * y[l]);
            seg[id].lsum = log2(x[l]);
            return;
        }
        int mm = l + r >> 1;
        build(l, mm, id * 2);
        build(mm + 1, r, id * 2 + 1);
        merge(id);
    }
    void m(int l, int r, int id, int p){
        if(l == r){
            seg[id].mx = (ll)x[l] * y[l] % mod;
            seg[id].sum = x[l];
            seg[id].lmx = log2((ll)x[l] * y[l]);
            seg[id].lsum = log2(x[l]);
            return ;
        }
        int mm = l + r >> 1;
        if(p <= mm){
            m(l, mm, id * 2, p);
        }
        else{
            m(mm + 1, r, id * 2 + 1, p);
        }
        merge(id);
    }
}tr;
int init(int N, int X[], int Y[]){
    n = N;
    for(int i = 1; i <= n; i++){
        x[i] = X[i - 1];
        y[i] = Y[i - 1];
    }
    tr.build(1, n, 1);
    return tr.seg[1].mx;
}
int updateX(int pos, int val){
    x[++pos] = val;
    tr.m(1, n, 1, pos);
    return tr.seg[1].mx;
}
int updateY(int pos, int val){
    y[++pos] = val;
    tr.m(1, n, 1, pos);
    return tr.seg[1].mx;
}

Compilation message

horses.cpp: In member function 'void segtree::build(int, int, int)':
horses.cpp:47:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |         int mm = l + r >> 1;
      |                  ~~^~~
horses.cpp: In member function 'void segtree::m(int, int, int, int)':
horses.cpp:60:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |         int mm = l + r >> 1;
      |                  ~~^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:77:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   77 |     return tr.seg[1].mx;
      |            ~~~~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:82:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   82 |     return tr.seg[1].mx;
      |            ~~~~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:87:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   87 |     return tr.seg[1].mx;
      |            ~~~~~~~~~~^~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 42068 KB Output is correct
2 Correct 114 ms 54608 KB Output is correct
3 Correct 86 ms 45744 KB Output is correct
4 Correct 103 ms 49640 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 448 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 53 ms 44884 KB Output is correct
34 Correct 51 ms 44992 KB Output is correct
35 Correct 71 ms 52048 KB Output is correct
36 Correct 69 ms 51812 KB Output is correct
37 Correct 35 ms 43096 KB Output is correct
38 Correct 43 ms 44116 KB Output is correct
39 Correct 33 ms 43092 KB Output is correct
40 Correct 61 ms 46960 KB Output is correct
41 Correct 31 ms 43096 KB Output is correct
42 Correct 31 ms 43224 KB Output is correct
43 Correct 49 ms 47444 KB Output is correct
44 Correct 46 ms 47268 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 600 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 59 ms 45836 KB Output is correct
34 Correct 110 ms 54488 KB Output is correct
35 Correct 77 ms 45648 KB Output is correct
36 Correct 97 ms 49672 KB Output is correct
37 Correct 46 ms 45108 KB Output is correct
38 Correct 48 ms 44884 KB Output is correct
39 Correct 73 ms 52048 KB Output is correct
40 Correct 68 ms 51876 KB Output is correct
41 Correct 33 ms 43292 KB Output is correct
42 Correct 40 ms 44116 KB Output is correct
43 Correct 31 ms 43156 KB Output is correct
44 Correct 49 ms 46928 KB Output is correct
45 Correct 29 ms 43100 KB Output is correct
46 Correct 32 ms 43344 KB Output is correct
47 Correct 51 ms 47440 KB Output is correct
48 Correct 45 ms 47440 KB Output is correct
49 Correct 91 ms 46920 KB Output is correct
50 Correct 99 ms 46944 KB Output is correct
51 Correct 95 ms 53844 KB Output is correct
52 Correct 93 ms 53332 KB Output is correct
53 Correct 84 ms 45452 KB Output is correct
54 Correct 70 ms 45900 KB Output is correct
55 Correct 50 ms 44116 KB Output is correct
56 Correct 77 ms 48720 KB Output is correct
57 Correct 49 ms 44624 KB Output is correct
58 Correct 53 ms 45136 KB Output is correct
59 Correct 51 ms 47432 KB Output is correct