Submission #1088254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088254		yeediot	Horses (IOI15_horses)	C++17	100 / 100	114 ms	54608 KiB

horses

#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 (stderr)

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 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 23 / 23