제출 #160688

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
160688		davitmarg	말 (IOI15_horses)	C++17	17 / 100	806 ms	34312 KiB

horses

/*DavitMarg*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <list>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;
#ifndef death
	#include "horses.h"
#endif

const int N=500005;

int n,x[N],y[N];
LL t[4*N],m[4*N],d[4*N];

void build(int v,int l,int r)
{
	t[v]=d[v]=m[v]=1;
    if(l==r)
		return;
    int mid=(l+r)/2;
    build(v*2,l,mid);
    build(v*2+1,mid+1,r);
}

void push(int v,int l,int r,bool f=1)
{
	if(d[v]==m[v])
	{
		d[v]=m[v]=1;
		return;
	}
    if(l!=r)
	{
		d[v*2]*=d[v];
		d[v*2+1]*=d[v];
		m[v*2]*=m[v];
		m[v*2+1]*=m[v];
		if(f)
		{
            int mid=(l+r)/2;
            push(v*2,l,mid,0);
            push(v*2+1,mid+1,r,0);
		}
	}
	t[v]/=m[v];
	t[v]*=d[v];
	d[v]=m[v]=1;
}

void upd(int v,int l,int r,int i,int j,int dv,int mv)
{
    push(v,l,r);
    if(i>j)
		return;
	if(l==i && r==j)
	{
        d[v]*=dv;
        m[v]*=mv;
		push(v,l,r);
		return;
	}
	int mid=(l+r)/2;
    upd(v*2,l,mid,i,min(j,mid),dv,mv);
    upd(v*2+1,mid+1,r,max(i,mid+1),j,dv,mv);
    t[v]=max(t[v*2],t[v*2+1]);
}

LL get(int v,int l,int r,int i,int j)
{
    push(v,l,r);
    if(i>j)
		return 0;
	if(l==i && r==j)
		return t[v];
	int mid=(l+r)/2;
	return max(
		get(v*2,l,mid,i,min(j,mid)),
		get(v*2+1,mid+1,r,max(i,mid+1),j));
}

int updateX(int pos,int val)
{
    upd(1,0,n-1,pos,n-1,val,x[pos]);
    x[pos]=val;
	return get(1,0,n-1,0,n-1)%mod;
}

int updateY(int pos,int val)
{
    upd(1,0,n-1,pos,pos,val,y[pos]);
    y[pos]=val;
	return get(1,0,n-1,0,n-1)%mod;
}


int init(int N,int X[],int Y[])
{
	n=N;
	for(int i=0;i<n;i++)
	{
		x[i]=X[i];
		y[i]=Y[i];
	}
	build(1,0,n-1);
	for(int i=0;i<n;i++)
	{
        upd(1,0,n-1,i,n-1,x[i],1);
        upd(1,0,n-1,i,i,y[i],1);
	}
	return get(1,0,n-1,0,n-1)%mod;
}



#ifdef death

int main()
{
    int N,X[102],Y[102],M;
    cin>>N;
    for(int i=0;i<N;i++)
		cin>>X[i];
    for(int i=0;i<N;i++)
		cin>>Y[i];
	cout<<init(N,X,Y)<<endl;
    cin>>M;
    while(M--)
	{
		int TYPE,POS,VAL;
		cin>>TYPE>>POS>>VAL;
        if(TYPE==1)
            cout<<updateX(POS,VAL)<<endl;
		else
            cout<<updateY(POS,VAL)<<endl;
	}

    return 0;
}

#endif

/*

2
2 1
3 4
0


*/

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

horses.cpp: In function 'int updateX(int, int)':
horses.cpp:107:27: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return get(1,0,n-1,0,n-1)%mod;
                           ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:114:27: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return get(1,0,n-1,0,n-1)%mod;
                           ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:118:31: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int init(int N,int X[],int Y[])
                               ^
horses.cpp:32:11: note: shadowed declaration is here
 const int N=500005;
           ^
horses.cpp:132:27: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return get(1,0,n-1,0,n-1)%mod;
                           ^

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