제출 #833868

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
833868		Victor	말 (IOI15_horses)	C++17	54 / 100	321 ms	138248 KiB

horses

#include "horses.h"

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

#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define per(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back

typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

const ll INF = 1'000'000'007;

struct Node {
    ll lo,hi,id;
    double log_sum=0,val,madd=0;
    Node *l,*r;
    Node(const vll&x, const vll&y, double add, ll L,ll R) : lo(L), hi(R) {
        if(hi-lo==1) {
            log_sum=logf64(x[lo])+add;
            val=log_sum+logf64(y[lo]);
            id=lo;

        } else {
            ll mid=(lo+hi)/2;
            l=new Node(x,y,add,lo,mid);
            r=new Node(x,y,l->log_sum,mid,hi);
            log_sum=r->log_sum;
            tie(val,id)=max(pair<double,ll>(l->val,l->id),pair<double,ll>(r->val,r->id));
        }
        //cout<<"lo = "<<lo<<" hi = "<<hi<<" log_sum = "<<log_sum<<" add = "<<add<<" val = "<<val<<endl;
    }


    void updateX(ll pos, double v) { // v is differnce between new x[pos] - prev x[pos]
        if(hi<=pos) return;
        if(pos<=lo) {
            madd+=v;
            log_sum+=v;
            val+=v;
            return;
        }

        push();
        l->updateX(pos,v);
        r->updateX(pos,v);
        tie(val,id)=max(pair<double,ll>(l->val,l->id),pair<double,ll>(r->val,r->id));
    }

    void updateY(ll pos, ll v) { // v is new y[pos]
        if(pos<lo||hi<=pos) return;
        if(hi-lo==1) {
            val=log_sum+logf64(v);
            return;
        }

        push();
        l->updateY(pos,v);
        r->updateY(pos,v);
        tie(val,id)=max(pair<double,ll>(l->val,l->id),pair<double,ll>(r->val,r->id));
    }

    void push() {
        if(madd!=0) {
            l->updateX(0,madd);
            r->updateX(0,madd);
            madd=0;
        }
    }
};

struct Prod {
    ll lo,hi,prod;
    Prod *l,*r;
    Prod(const vll&x,ll L,ll R) : lo(L), hi(R) {
        if(hi-lo==1) {
            prod=x[lo];

        } else {
            ll mid=(lo+hi)/2;
            l=new Prod(x,lo,mid);
            r=new Prod(x,mid,hi);
            prod=l->prod*r->prod%INF;
        }
    }

    ll query(ll R) {
        if(R<=lo) return 1;
        if(hi<=R) return prod;
        return l->query(R)*r->query(R)%INF;
    }

    void updateX(ll pos,ll v) { // v is new x[pos]
        if(pos<lo||hi<=pos) return; 
        if(hi-lo==1) {
            prod=v;
            return;
        }

        l->updateX(pos,v);
        r->updateX(pos,v);
        prod=l->prod*r->prod%INF;
    }
};

vll x,y;
Node *segtree;
Prod *prodseg;

int init(int N, int X[], int Y[]) {
    rep(i,0,N) {
        assert(X[i]&&Y[i]);
        x.pb(X[i]);
        y.pb(Y[i]);
    }

    segtree=new Node(x,y,0,0,N);
    prodseg=new Prod(x,0,N);

    ll id=segtree->id;
    return prodseg->query(id+1)*y[id]%INF;
}

int updateX(int pos, int val) {
    assert(val);
    double diff=logf64(val)-logf64(x[pos]);
    x[pos]=val;
    segtree->updateX(pos,diff);
    prodseg->updateX(pos,val);
    ll id=segtree->id;
    return prodseg->query(id+1)*y[id]%INF;
}

int updateY(int pos, int val) {
    assert(val);
    y[pos]=val;
    segtree->updateY(pos,val);
    ll id=segtree->id;
    return prodseg->query(id+1)*y[id]%INF;
}
/*
#include "horses.h"
#include <stdio.h>
#include <stdlib.h>

static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;
static FILE *_inputFile, *_outputFile;

static inline int _read() {
    if (_charsNumber < 0) {
        exit(1);
    }
    if (!_charsNumber || _currentChar == _charsNumber) {
        _charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
        _currentChar = 0;
    }
    if (_charsNumber <= 0) {
        return -1;
    }
    return _buffer[_currentChar++];
}

static inline int _readInt() {
    int c, X, s;
    c = _read();
    while (c <= 32) c = _read();
    X = 0;
    s = 1;
    if (c == '-') {
        s = -1;
        c = _read();
    }
    while (c > 32) {
        X *= 10;
        X += c - '0';
        c = _read();
    }
    if (s < 0) X = -X;
    return X;
}


int main() {
	_inputFile = fopen("horses.in", "rb");
	
	int N; N = _readInt();

	int *X = (int*)malloc(sizeof(int)*(unsigned int)N);
	int *Y = (int*)malloc(sizeof(int)*(unsigned int)N);

	for (int i = 0; i < N; i++) {
		X[i] = _readInt();
	}

	for (int i = 0; i < N; i++) {
		Y[i] = _readInt();
	}	

	printf("%d\n",init(N,X,Y));

	int M; M = _readInt();

	for (int i = 0; i < M; i++) {
		int type; type = _readInt();
		int pos; pos = _readInt();
		int val; val = _readInt(); 

		if (type == 1) {
			printf("%d\n",updateX(pos,val));
		} else if (type == 2) {
			printf("%d\n",updateY(pos,val));
		}
	}

	return 0;
}*/

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

horses.cpp: In constructor 'Node::Node(const vll&, const vll&, double, ll, ll)':
horses.cpp:27:33: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to '_Float64' {aka 'double'} may change value [-Wconversion]
   27 |             log_sum=logf64(x[lo])+add;
      |                                 ^
horses.cpp:28:37: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to '_Float64' {aka 'double'} may change value [-Wconversion]
   28 |             val=log_sum+logf64(y[lo]);
      |                                     ^
horses.cpp: In member function 'void Node::updateY(ll, ll)':
horses.cpp:60:32: warning: conversion from 'll' {aka 'long long int'} to '_Float64' {aka 'double'} may change value [-Wconversion]
   60 |             val=log_sum+logf64(v);
      |                                ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:128:38: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  128 |     return prodseg->query(id+1)*y[id]%INF;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:133:42: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to '_Float64' {aka 'double'} may change value [-Wconversion]
  133 |     double diff=logf64(val)-logf64(x[pos]);
      |                                          ^
horses.cpp:138:38: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  138 |     return prodseg->query(id+1)*y[id]%INF;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:146:38: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  146 |     return prodseg->query(id+1)*y[id]%INF;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

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