제출 #310709

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
310709		keta_tsimakuridze	말 (IOI15_horses)	C++14	100 / 100	421 ms	63868 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+5,mod=1e9+7,Mx=1e9;
ll x[N],y[N],k,t,m,n;
struct node {
	ll l;
	ll r;
	ll Y;
	ll b;
	ll bl;
	ll br;
} tree[4*N];
void update(ll u,ll ind,ll l,int r,ll valx,ll valy) {
	if(l>ind || r<ind) return;
	if(l==r) {
		tree[u].l=valx;
		//	tree[u].X=valx;
		tree[u].Y=valy;
		tree[u].r=1;
		if(valx*valy>Mx) {
			tree[u].b=1;
		} else tree[u].b=0;
		return;
	}
	int mid=(l+r)/2;
	update(2*u,ind,l,mid,valx,valy);
	update(2*u+1,ind,mid+1,r,valx,valy);
	if(tree[2*u].br||tree[2*u+1].bl || tree[2*u].r*tree[2*u+1].l>Mx || tree[2*u].r*tree[2*u+1].l*tree[2*u+1].Y>tree[2*u].Y ) {
		// tree[2*u].l*tree[2*u].r*tree[2*u+1].l
		if(tree[2*u].b||tree[2*u+1].bl || tree[2*u].l*tree[2*u].r*tree[2*u+1].l>Mx) {
			tree[u].bl=1;
		} else tree[u].bl=0;
		tree[u].r=tree[2*u+1].r;
		tree[u].br=tree[2*u+1].br;
		tree[u].l=tree[2*u].l*tree[2*u].r%mod*tree[2*u+1].l%mod;
		if(tree[u].bl || tree[u].br || tree[u].l*tree[u].r>Mx) {
			tree[u].b=1;
		} else tree[u].b=0;
		tree[u].Y=tree[2*u+1].Y;
	} else {
		tree[u].l=tree[2*u].l;
		tree[u].bl=tree[2*u].bl;
		tree[u].Y=tree[2*u].Y;
		tree[u].r=tree[2*u+1].r*tree[2*u+1].l%mod*tree[2*u].r%mod;
		if(tree[2*u+1].b || tree[2*u].br  ||tree[2*u+1].r*tree[2*u+1].l*tree[2*u].r>Mx) {
			tree[u].br=1;
		} else tree[u].br=0;

		if(tree[u].br || tree[u].bl || tree[u].l*tree[u].r>Mx) {
			tree[u].b=1;
		} else tree[u].b=0;
	}
}
void go(int u,int l,int r) {
	cout<<l<<" "<<r<<" "<<tree[u].l<<" "<<tree[u].r<<" "<<tree[u].Y<<endl;
	if(l==r) {
		return;
	}
	int mid=(l+r)/2;
	go(2*u,l,mid);
	go(2*u+1,mid+1,r);
}
int init(int nn,int X[],int Y[]) {
	n=nn;
	for(k=1; k<=n; k++) {
		x[k]=X[k-1];
		y[k]=Y[k-1];
		update(1,k,1,n,x[k],y[k]);
	}
	//go(1,1,n);
    ll ans=tree[1].l*tree[1].Y%mod;
	return  ans;
}
int updateX(int ind,int c) {
	ind++;
	update(1,ind,1,n,c,y[ind]);
	x[ind]=c;
	ll ans=tree[1].l*tree[1].Y%mod;
	return  ans;
}
int updateY(int ind,int c){	
    ind++;
    update(1,ind,1,n,x[ind],c);
	y[ind]=c;
	ll ans=tree[1].l*tree[1].Y%mod;
	return  ans;
}

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

horses.cpp: In function 'void update(long long int, long long int, long long int, int, long long int, long long int)':
horses.cpp:27:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   27 |  int mid=(l+r)/2;
      |          ~~~~~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:70:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   70 |   update(1,k,1,n,x[k],y[k]);
      |                ^
horses.cpp:74:10: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   74 |  return  ans;
      |          ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:78:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   78 |  update(1,ind,1,n,c,y[ind]);
      |                 ^
horses.cpp:81:10: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   81 |  return  ans;
      |          ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:85:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   85 |     update(1,ind,1,n,x[ind],c);
      |                    ^
horses.cpp:88:10: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   88 |  return  ans;
      |          ^~~

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