Submission #876470

#	Time	Username	Problem	Language	Result	Execution time	Memory
876470		TahirAliyev	말 (IOI15_horses)	C++17	100 / 100	787 ms	36492 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int> 

const int MAX = 5e5 + 5, MOD = 1e9 + 7;


int n;
pii tree[4 * MAX];
int tree2[4 * MAX];
int x[MAX];
int y[MAX];

pii comb(pii a, pii b){
    pii c = {0, 0};
    if(a.first) c.first = 1;
    if(b.first) c.first = 1;
    if(1ll * a.second * b.second > 1e9) c.first = 1;
    c.second = (1ll * a.second * b.second) % MOD;
    return c;
}

void build(int node, int l, int r){
    if(l == r){
        tree[node] = {0, x[l]};
        return;
    }
    int mid = (l + r) / 2;
    build(2 * node, l, mid);
    build(2 * node + 1, mid + 1, r);
    tree[node] = comb(tree[2 * node], tree[2 * node + 1]);
}

void updatex(int node, int l, int r, int pos, int val){
    if(l == r){
        tree[node] = {0, val};
        return;
    }
    int mid = (l + r) / 2;
    if(pos <= mid){
        updatex(2 * node, l, mid, pos, val);
    }
    else{
        updatex(2 * node + 1, mid + 1, r, pos, val);
    }
    tree[node] = comb(tree[2 * node], tree[2 * node + 1]);
}

pii mult(int node, int l, int r, int ql, int qr){
    if(qr < l || r < ql) return {0, 1};
    if(ql <= l && r <= qr) return tree[node];
    int mid = (l + r) / 2;
    return comb(mult(2 * node, l, mid, ql, qr), mult(2 * node + 1, mid + 1, r, ql, qr));
}

int comb2(int a, int b){
    if(b > a) swap(a, b);
    pii m = mult(1, 0, n - 1, b + 1, a);
    if(m.first) return a;
    if(1ll * m.second * y[a] > y[b]) return a;
    return b;
}

void build2(int node, int l, int r){
    if(l == r){
        tree2[node] = l;
        return;
    }
    int mid = (l + r) / 2;
    build2(2 * node, l, mid);
    build2(2 * node + 1, mid + 1, r);
    tree2[node] = comb2(tree2[2 * node], tree2[2 * node + 1]);
}

void updatey(int node, int l, int r, int pos){
    if(l == r) return;
    int mid = (l + r) / 2;
    if(pos <= mid){
        updatey(2 * node, l, mid, pos);
    }
    else{
        updatey(2 * node + 1, mid + 1, r, pos);
    }
    tree2[node] = comb2(tree2[2 * node], tree2[2 * node + 1]);
}

int init(int N, int X[], int Y[]){
    n = N;
    for(int i = 0; i < n; i++){
        x[i] = X[i];
        y[i] = Y[i];
    }
    build(1, 0, n - 1);
    build2(1, 0, n - 1);
    int id = tree2[1];
    return 1ll * mult(1, 0, n - 1, 0, id).second * y[id] % MOD;
}

int updateX(int pos, int val) {	
    x[pos] = val;
	updatex(1, 0, n - 1, pos, val);
    updatey(1, 0, n - 1, pos);
    int id = tree2[1];
    return 1ll * mult(1, 0, n - 1, 0, id).second * y[id] % MOD;
}

int updateY(int pos, int val) {
	y[pos] = val;
    updatey(1, 0, n - 1, pos);
    int id = tree2[1];
    return 1ll * mult(1, 0, n - 1, 0, id).second * y[id] % MOD;
}

Compilation message (stderr)

horses.cpp: In function 'std::pair<int, int> comb(std::pair<int, int>, std::pair<int, int>)':
horses.cpp:22:44: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   22 |     c.second = (1ll * a.second * b.second) % MOD;
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:99:58: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   99 |     return 1ll * mult(1, 0, n - 1, 0, id).second * y[id] % MOD;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:107:58: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  107 |     return 1ll * mult(1, 0, n - 1, 0, id).second * y[id] % MOD;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:114:58: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  114 |     return 1ll * mult(1, 0, n - 1, 0, id).second * y[id] % MOD;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 23 / 23