oj.uz

Submission #1088250

# Submission time Handle Problem Language Result Execution time Memory
1088250 2024-09-14T07:16:44 Z yeediot Horses (IOI15_horses) C++17
17 / 100
 61 ms 45772 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 = x[l] * y[l] % mod;
            seg[id].sum = x[l];
            seg[id].lmx = log2((ll)x[l] * y[l] % mod);
            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 = x[l] * y[l] % mod;
            seg[id].sum = x[l];
            seg[id].lmx = log2((ll)x[l] * y[l] % mod);
            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 1 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 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 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

Subtask #2
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 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 Incorrect 0 ms 344 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 45772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
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 444 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 448 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 Incorrect 0 ms 348 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 0 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
21 Incorrect 1 ms 348 KB Output isn't correct
22 Halted 0 ms 0 KB -