oj.uz

Submission #160688

# Submission time Handle Problem Language Result Execution time Memory
160688 2019-10-29T10:33:56 Z davitmarg Horses (IOI15_horses) C++17
17 / 100
 806 ms 34312 KB 
/*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


*/

Compilation message

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 7 ms 368 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 9 ms 376 KB Output is correct
11 Correct 8 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Incorrect 2 ms 376 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 806 ms 34312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 508 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 380 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Incorrect 2 ms 376 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 7 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 4 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 400 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Incorrect 2 ms 376 KB Output isn't correct
22 Halted 0 ms 0 KB -