답안 #31009 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
31009	2017-08-04T01:28:02 Z	kajebiii	말 (IOI15_horses)	C++14	17 / 100	229 ms	26428 KB

horses

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

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<double, double> pd;
typedef pair<int, int> pi;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF * 2;

const int MOD = 1e9 + 7;

int N, *X, *Y;
ll myMul(ll x, ll y) {
    if(x < MOD && y < MOD) return x*y;
    return LINF;
}
struct MUL{
    int P; vector<ll> val, mod;
    void merge(int i) {
        val[i] = myMul(val[i*2], val[i*2+1]);
        mod[i] = mod[i*2] * mod[i*2+1] % MOD;
    }
    MUL() {}
    MUL(int n, int nr[]) {
        for(P=1; P<n; P<<=1);
        val = mod = vector<ll>(2*P, 1);
        for(int i=0; i<n; i++) val[P+i] = mod[P+i] = nr[i];
        for(int i=P-1; i>=1; i--) merge(i);
    }
    void updateX(int v, int k) {
        X[v] = k;
        v += P;
        val[v] = mod[v] = k;
        while(v/=2) merge(v);
    }
    ll getMul(int a, int b) {
        ll res = 1;
        for(a+=P, b+=P; a<=b; a>>=1, b>>=1) {
            if(a%2==1) res = myMul(res, val[a++]);
            if(b%2==0) res = myMul(res, val[b--]);
        }
        return res;
    }
    ll getMod(int a, int b) {
        ll res = 1;
        for(a+=P, b+=P; a<=b; a>>=1, b>>=1) {
            if(a%2==1) res = res * mod[a++] % MOD;
            if(b%2==0) res = res * mod[b--] % MOD;
        }
        return res;
    }
}Mul;

struct IDX{
    int P; vector<int> ix;
    void merge(int i) {
        int l = ix[i*2], r = ix[i*2+1];
        int res = -1;
        if(r == -1) res = l;
        else{
            ll mul = Mul.getMul(l+1, r);
            if(mul >= MOD) res = r;
            else{
                if(Y[l] >= mul * Y[r]) res = l;
                else res = r;
            }
        }
        ix[i] = res;
    }
    IDX() {}
    IDX(int n, int nr[]) {
        for(P=1; P<n; P<<=1);
        ix = vector<int>(2*P, -1);
        for(int i=0; i<n; i++) ix[P+i] = i;
        for(int i=P-1; i>=1; i--) merge(i);
    }
    void updateY(int v, int k) {
        Y[v] = k;
        v += P;
        while(v/=2) merge(v);
    }
    int getMax() {return ix[1];}
}Idx;
int getAns() {
    int ans = Idx.getMax();
    return Mul.getMod(0, ans) * Y[ans] % MOD;
}
int init(int n, int x[], int y[]) {
    N = n; X = x; Y = y;
    Mul = MUL(n, x);
    Idx = IDX(n, y);
	return getAns();
}

int updateX(int pos, int val) {	
    Mul.updateX(pos, val);
	return getAns();
}

int updateY(int pos, int val) {
    Idx.updateY(pos, val);
	return getAns();
}

Compilation message

horses.cpp:81:23: warning: unused parameter 'nr' [-Wunused-parameter]
     IDX(int n, int nr[]) {
                       ^
horses.cpp: In function 'int getAns()':
horses.cpp:96:42: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
     return Mul.getMod(0, ans) * Y[ans] % MOD;
                                          ^

Subtask #1
17.0 / 17.0

#	결과	메모리	Grader output
1	Correct	2024 KB	Output is correct
2	Correct	2024 KB	Output is correct
3	Correct	2024 KB	Output is correct
4	Correct	2024 KB	Output is correct
5	Correct	2024 KB	Output is correct
6	Correct	2024 KB	Output is correct
7	Correct	2024 KB	Output is correct
8	Correct	2024 KB	Output is correct
9	Correct	2024 KB	Output is correct
10	Correct	2024 KB	Output is correct
11	Correct	2024 KB	Output is correct
12	Correct	2024 KB	Output is correct
13	Correct	2024 KB	Output is correct
14	Correct	2024 KB	Output is correct
15	Correct	2024 KB	Output is correct
16	Correct	2024 KB	Output is correct
17	Correct	2024 KB	Output is correct
18	Correct	2024 KB	Output is correct
19	Correct	2024 KB	Output is correct
20	Correct	2024 KB	Output is correct

Subtask #2
0 / 17.0

#	결과	메모리	Grader output
1	Correct	2024 KB	Output is correct
2	Correct	2024 KB	Output is correct
3	Correct	2024 KB	Output is correct
4	Correct	2024 KB	Output is correct
5	Correct	2024 KB	Output is correct
6	Correct	2024 KB	Output is correct
7	Correct	2024 KB	Output is correct
8	Correct	2024 KB	Output is correct
9	Correct	2024 KB	Output is correct
10	Correct	2024 KB	Output is correct
11	Correct	2024 KB	Output is correct
12	Correct	2024 KB	Output is correct
13	Correct	2024 KB	Output is correct
14	Correct	2024 KB	Output is correct
15	Correct	2024 KB	Output is correct
16	Correct	2024 KB	Output is correct
17	Correct	2024 KB	Output is correct
18	Correct	2024 KB	Output is correct
19	Correct	2024 KB	Output is correct
20	Correct	2024 KB	Output is correct
21	Incorrect	2024 KB	Output isn't correct
22	Halted	0 KB	-

Subtask #3
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	86 ms	26428 KB	Output is correct
2	Correct	133 ms	26428 KB	Output is correct
3	Correct	229 ms	26428 KB	Output is correct
4	Incorrect	139 ms	26428 KB	Output isn't correct

Subtask #4
0 / 23.0

#	결과	메모리	Grader output
1	Correct	2024 KB	Output is correct
2	Correct	2024 KB	Output is correct
3	Correct	2024 KB	Output is correct
4	Correct	2024 KB	Output is correct
5	Correct	2024 KB	Output is correct
6	Correct	2024 KB	Output is correct
7	Correct	2024 KB	Output is correct
8	Correct	2024 KB	Output is correct
9	Correct	2024 KB	Output is correct
10	Correct	2024 KB	Output is correct
11	Correct	2024 KB	Output is correct
12	Correct	2024 KB	Output is correct
13	Correct	2024 KB	Output is correct
14	Correct	2024 KB	Output is correct
15	Correct	2024 KB	Output is correct
16	Correct	2024 KB	Output is correct
17	Correct	2024 KB	Output is correct
18	Correct	2024 KB	Output is correct
19	Correct	2024 KB	Output is correct
20	Correct	2024 KB	Output is correct
21	Incorrect	2024 KB	Output isn't correct
22	Halted	0 KB	-

Subtask #5
0 / 23.0

#	결과	메모리	Grader output
1	Correct	2024 KB	Output is correct
2	Correct	2024 KB	Output is correct
3	Correct	2024 KB	Output is correct
4	Correct	2024 KB	Output is correct
5	Correct	2024 KB	Output is correct
6	Correct	2024 KB	Output is correct
7	Correct	2024 KB	Output is correct
8	Correct	2024 KB	Output is correct
9	Correct	2024 KB	Output is correct
10	Correct	2024 KB	Output is correct
11	Correct	2024 KB	Output is correct
12	Correct	2024 KB	Output is correct
13	Correct	2024 KB	Output is correct
14	Correct	2024 KB	Output is correct
15	Correct	2024 KB	Output is correct
16	Correct	2024 KB	Output is correct
17	Correct	2024 KB	Output is correct
18	Correct	2024 KB	Output is correct
19	Correct	2024 KB	Output is correct
20	Correct	2024 KB	Output is correct
21	Incorrect	2024 KB	Output isn't correct
22	Halted	0 KB	-

답안 #31009

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 0 / 17.0

Subtask #3 0 / 20.0

Subtask #4 0 / 23.0

Subtask #5 0 / 23.0

Subtask #1
17.0 / 17.0

Subtask #2
0 / 17.0

Subtask #3
0 / 20.0

Subtask #4
0 / 23.0

Subtask #5
0 / 23.0