Submission #432995

#	Time	Username	Problem	Language	Result	Execution time	Memory
432995		timmyfeng	Horses (IOI15_horses)	C++17	100 / 100	259 ms	80384 KiB

horses

#include <bits/stdc++.h>
using namespace std;

#include "horses.h"

const int M = 1000000007;

struct mint {
    int value;
    bool mod;

    mint(int x = 0, bool y = false) {
        value = x, mod = y;
    }

    friend mint operator*(mint l, mint r) {
        long long product = (long long) l.value * r.value;
        return mint(product % M, product >= M || l.mod || r.mod);
    }
};

struct segtree {
    segtree *left, *right;
    mint product, suffix, price, value;

    void pull() {
        product = left->product * right->product;
        mint temp = right->value * left->suffix;
        if (temp.mod || temp.value > left->price.value) {
            suffix = right->suffix;
            price = right->price;
            value = right->value * left->product;
        } else {
            suffix = left->suffix * right->product;
            price = left->price;
            value = left->value;
        }
    }

    segtree(int l, int r, int x[], int y[]) {
        if (l == r) {
            product = x[l];
            price = y[l];
            suffix = 1;
            value = product * price;
        } else {
            int m = (l + r) / 2;
            left = new segtree(l, m, x, y);
            right = new segtree(m + 1, r, x, y);
            pull();
        }
    }

    void update(int a, int x, int y, int l, int r) {
        if (l == r) {
            product = x > 0 ? mint(x) : product;
            price = y > 0 ? mint(y) : price;
            value = product * price;
        } else {
            int m = (l + r) / 2;
            if (a <= m) {
                left->update(a, x, y, l, m);
            } else {
                right->update(a, x, y, m + 1, r);
            }
            pull();
        }
    }
};

segtree *ans;
int n;

int init(int N, int X[], int Y[]) {
    ans = new segtree(0, N - 1, X, Y), n = N;
	return ans->value.value;
}

int updateX(int pos, int val) {
    ans->update(pos, val, 0, 0, n - 1);
    return ans->value.value;
}

int updateY(int pos, int val) {
    ans->update(pos, 0, val, 0, n - 1);
    return ans->value.value;
}

Compilation message (stderr)

horses.cpp: In function 'mint operator*(mint, mint)':
horses.cpp:18:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   18 |         return mint(product % M, product >= M || l.mod || r.mod);
      |                     ~~~~~~~~^~~

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