oj.uz

Submission #74014

# Submission time Handle Problem Language Result Execution time Memory
74014 2018-08-29T15:41:09 Z aleksam Horses (IOI15_horses) C++14
17 / 100
 1500 ms 48344 KB 
#include "horses.h"
#include <bits/stdc++.h>
#define MAX_N 500000
#define MOD 1000000007
#define INF 1000000000
#define debug 0
using namespace std;

int segtree[4*MAX_N], N;
long long X[MAX_N], Y[MAX_N];
long long partX[4*MAX_N];

struct classcomp {
  bool operator() (const int& lhs, const int& rhs) const
  {return lhs>rhs;}
};

set<int> S;//Skup indexa na kojima X[i]>1

void maketree(int l, int r, int v){
	if(l+1>=r){
		if(l==r-1){
			segtree[v]=l;
			partX[v]=X[l];
			return;
		}
		/*segtree[v]=-1;
		partX[v]=1;*/
		assert(0);
		return;
	}
	int mid=(l+r)/2;
	maketree(l, mid, 2*v+1);
	maketree(mid, r, 2*v+2);
	partX[v]=partX[2*v+1]*partX[2*v+2];
	partX[v]%=MOD;
	if(segtree[2*v+1]==-1){
		segtree[v]=segtree[2*v+2];
		return;
	}
	if(segtree[2*v+2]==-1){
		segtree[v]=segtree[2*v+1];
		return;
	}
	segtree[v]=Y[segtree[2*v+1]]>Y[segtree[2*v+2]]?segtree[2*v+1]:segtree[2*v+2];
	return;
}

int query(int ql, int qr, int l, int r, int v){
	//if(debug)printf("rmq(%d, %d, %d, %d)\n", ql, qr, l, r);
	if(ql>=r || qr<=l){
		return -1;
	}
	if(ql<=l  && r<=qr){
		return segtree[v];
	}
	int q1, q2;
	q1=query(ql, qr, l, (l+r)/2, 2*v+1);
	q2=query(ql, qr, (l+r)/2, r, 2*v+2);
	if(q1==-1)return q2;
	if(q2==-1)return q1;
	return Y[q1]>Y[q2]?q1:q2;
}

int partquery(int ql, int qr, int l, int r, int v){
	if(ql>=r || qr<=l){
		return -1;
	}
	if(ql<=l  && r<=qr){
		return partX[v];
	}
	long long q1, q2;
	q1=partquery(ql, qr, l, (l+r)/2, 2*v+1);
	q2=partquery(ql, qr, (l+r)/2, r, 2*v+2);
	return (q1*q2)%MOD;
}

int rmq(int ql, int qr){//Vraca index!!!
	//printf("rmq(%d, %d)\n", ql, qr);
	int max=0, indmax=-1;
	for(int i=ql; i<qr; ++i){
		if(Y[i]>max){
			max=Y[i];
			indmax=i;
		}
	}
	return indmax;
	//return query(ql, qr, 0, N, 0);
}

int partXX(int pos){
	long long ret=1;
	for(int i=0; i<pos+1; ++i){
		ret*=X[i];
		if(ret>MOD)ret%=MOD;
	}
	return ret;
	//return partquery(0, pos+1, 0, N, 0);
}

void updatetree(int l, int r, int v, int x){
	if(l+1>=r){
		return;
	}
	if(l<=x && x<r){
		updatetree(l, (l+r)/2, 2*v+1, x);
		updatetree((l+r)/2, r, 2*v+2, x);
		if(segtree[2*v+1]==-1){
			segtree[v]=segtree[2*v+2];
			return;
		}
		if(segtree[2*v+2]==-1){
			segtree[v]=segtree[2*v+1];
			return;
		}
		segtree[v]=Y[segtree[2*v+1]]>Y[segtree[2*v+2]]?segtree[2*v+1]:segtree[2*v+2];
	}
}

void updatepart(int l, int r, int v, int x){
	if(l+1>=r){
		return;
	}
	if(l<=x && x<r){
		updatetree(l, (l+r)/2, 2*v+1, x);
		updatetree((l+r)/2, r, 2*v+2, x);
		partX[v]=(partX[2*v+1]*partX[2*v+2])%MOD;
	}
}
vector<int> big;//Indexi svih X-eva koji su veci od 1
int num_big=0;

int solve(){
	big.clear();//Moze brze
	long long pi=1;
	if(partXX(N-1)<INF)big.push_back(0);
	for(auto i:S){
		pi*=X[i];
		big.push_back(i);
		if(pi>INF)break;
	}
	
	pi=1;
	int d=big.size();
	if(debug){
		for(int i=0; i<d; ++i)printf("%d ", big[i]);
		printf("\n");
	}
	long long totmax=0, indmax=-1;
	for(int i=0; i<d; ++i){
		long long maxy;
		if(i!=d-1){
			maxy=rmq(big[i], big[i+1]);
		}
		else {
			maxy=rmq(big[i], N);
			//printf("ovde\n");
		}
		if(debug){printf("Iteracija i=%d, big[i]=%d, maxy=%d, pi=%d\n", i, big[i], maxy, pi);}
		if(i!=0)pi*=X[big[i]];
		if((long long)Y[maxy]*pi>totmax){
			totmax=(long long)Y[maxy]*pi;
			indmax=maxy;
		}
		
	}
	if(debug){
		printf("totmax=%d, indmax=%d\n", totmax, indmax);
		printf("partXX(indmax)=%d\n", partXX(indmax));
	}
	long long res=(long long)Y[indmax]*partXX(indmax);
	return res%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];
		if(X[i]>1){
			S.insert(i);
			num_big++;
		}
	}
	maketree(0, N, 0);
	if(debug){
		for(int i=0; i<4*N; ++i){
			printf("%*d ", 3, i);
		}
		printf("\n");
		for(int i=0; i<4*N; ++i){	
			printf("%*d ", 3, segtree[i]);
		}
		printf("\n");
		for(int i=0; i<4*N; ++i){
			printf("%*d ", 3, partX[i]);
		}
		printf("\n");
	}
	
	return solve();
}

int updateX(int pos, int val) {
	if(X[pos]==1 && val>1){
		S.insert(pos);
		X[pos]=val;
		updatepart(0, N, 0, pos);
	}
	else if(X[pos]>1 && val==1){
		S.erase(pos);
		X[pos]=1;
		updatepart(0, N, 0, pos);
	}
	else if(X[pos]>1 && val>1){
		X[pos]=val;
		updatepart(0, N, 0, pos);
	}
	return solve();
}

int updateY(int pos, int val) {
	Y[pos]=val;
	updatetree(0, N, 0, pos);
	return solve();
}

Compilation message

horses.cpp: In function 'int partquery(int, int, int, int, int)':
horses.cpp:70:17: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   return partX[v];
          ~~~~~~~^
horses.cpp:75:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return (q1*q2)%MOD;
                ^
horses.cpp: In function 'int rmq(int, int)':
horses.cpp:83:11: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
    max=Y[i];
        ~~~^
horses.cpp: In function 'int partXX(int)':
horses.cpp:97:9: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return ret;
         ^~~
horses.cpp: In function 'int solve()':
horses.cpp:144:16: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  int d=big.size();
        ~~~~~~~~^~
horses.cpp:159:86: warning: format '%d' expects argument of type 'int', but argument 4 has type 'long long int' [-Wformat=]
   if(debug){printf("Iteracija i=%d, big[i]=%d, maxy=%d, pi=%d\n", i, big[i], maxy, pi);}
                                                                                      ^
horses.cpp:159:86: warning: format '%d' expects argument of type 'int', but argument 5 has type 'long long int' [-Wformat=]
horses.cpp:168:50: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   printf("totmax=%d, indmax=%d\n", totmax, indmax);
                                                  ^
horses.cpp:168:50: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
horses.cpp:169:46: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   printf("partXX(indmax)=%d\n", partXX(indmax));
                                              ^
horses.cpp:171:50: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  long long res=(long long)Y[indmax]*partXX(indmax);
                                                  ^
horses.cpp:172:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return res%MOD;
            ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:196:30: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
    printf("%*d ", 3, partX[i]);
                      ~~~~~~~~^

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 17.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1546 ms 48344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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