제출 #1041317

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1041317		allin27x	말 (IOI15_horses)	C++17	100 / 100	261 ms	66640 KiB

horses

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9+7;
 
struct node{
    int l=1,r=1,lm=1,rm=1,y=1;
};

const int N = 5e5+5;
node t[4*N];
int X[N], Y[N];


node merge(node a, node b){
    node res; 
    int p = a.r * b.l; if (p>1e9) p = 0;
    if (!p || p * b.y > a.y){
        res.y = b.y;
        res.l = a.l * a.r; if (res.l>1e9) res.l = 0; res.l*=b.l; if (res.l>1e9) res.l = 0;
        res.r = b.r; res.rm = b.rm;
        res.lm = (a.lm*a.rm)%mod; res.lm*=b.lm; res.lm%=mod; 
    } else {
        res.y = a.y; res.l=a.l; res.lm=a.lm;
        res.r = b.l * b.r; if (res.r>1e9) res.r = 0; res.r*=a.r; if (res.r>1e9) res.r = 0;
        res.rm=(b.lm*b.rm)%mod; res.rm*=a.rm; res.rm%=mod;
    }
    return res;
}

void update(int p, int l, int r, int i){
    if (l==r){
        t[p].l=X[i]; t[p].lm=X[i]; t[p].y=Y[i];
        return;
    }
    int m = l + r >> 1;
    if (m>=i) update(2*p, l, m, i); 
    else update(2*p+1, m+1, r, i);
    t[p] = merge(t[2*p], t[2*p+1]);
}


signed init(signed n, signed x[], signed y[]){
	for (int i=0; i<n; i++) X[i] = x[i], Y[i]=y[i];
    for (int i=0; i<n; i++) update(1, 0, N-1, i);
    return (t[1].lm*t[1].y) % mod;
}

signed updateX(signed pos, signed val){
	X[pos] = val; update(1, 0, N-1, pos);
    return (t[1].lm*t[1].y) % mod;
}

signed updateY(signed pos, signed val){
	Y[pos] = val; update(1, 0, N-1, pos);
    return (t[1].lm*t[1].y) % mod;
}
 

컴파일 시 표준 에러 (stderr) 메시지

horses.cpp: In function 'node merge(node, node)':
horses.cpp:17:28: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   17 |     int p = a.r * b.l; if (p>1e9) p = 0;
      |                            ^
horses.cpp:20:36: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   20 |         res.l = a.l * a.r; if (res.l>1e9) res.l = 0; res.l*=b.l; if (res.l>1e9) res.l = 0;
      |                                ~~~~^
horses.cpp:20:74: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   20 |         res.l = a.l * a.r; if (res.l>1e9) res.l = 0; res.l*=b.l; if (res.l>1e9) res.l = 0;
      |                                                                      ~~~~^
horses.cpp:25:36: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   25 |         res.r = b.l * b.r; if (res.r>1e9) res.r = 0; res.r*=a.r; if (res.r>1e9) res.r = 0;
      |                                ~~~~^
horses.cpp:25:74: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   25 |         res.r = b.l * b.r; if (res.r>1e9) res.r = 0; res.r*=a.r; if (res.r>1e9) res.r = 0;
      |                                                                      ~~~~^
horses.cpp: In function 'void update(long long int, long long int, long long int, long long int)':
horses.cpp:36:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |     int m = l + r >> 1;
      |             ~~^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:46:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   46 |     return (t[1].lm*t[1].y) % mod;
      |            ~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:51:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   51 |     return (t[1].lm*t[1].y) % mod;
      |            ~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:56:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   56 |     return (t[1].lm*t[1].y) % mod;
      |            ~~~~~~~~~~~~~~~~~^~~~~

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