oj.uz

답안 #65359

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
65359 2018-08-07T12:37:22 Z hamzqq9 말 (IOI15_horses) C++14
17 / 100
 1500 ms 44360 KB 
#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define st first
#define nd second
#define orta ((bas+son)>>1)
#define ii pair<int,int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long


struct day {

	int l,r;
	int xpro;
	int mxy;

	day(int a,int b,int c,int d) {

		l=a;r=b;xpro=c;mxy=d;

	}

	bool operator<(const day& oth) const {

		return r<oth.r;

	}

	bool operator>(const day& oth) const {

		return r>oth.r;

	}

};

set<day> S;
int N;
int X[500005];
int seg[500005*4],tut[500005];
int allpro=1;

int fe(int x,int y) {

	int res=1;
	int cur=x;

	while(y) {

		if(y&1) res=1ll*res*cur%MOD;

		y>>=1;

		cur=1ll*cur*cur%MOD;

	}

	return res;

}

int get(int node,int bas,int son,int x,int y) {

	if(bas>=x && son<=y) return seg[node];

	if(orta>=x && orta+1<=y) return max(get(node*2,bas,orta,x,y),get(node*2+1,orta+1,son,x,y));
	if(orta>=x) return get(node*2,bas,orta,x,y);
	if(orta+1<=y) return get(node*2+1,orta+1,son,x,y);

}

void up(int pos,int val) {

	seg[tut[pos]]=val;

	for(int node=tut[pos]>>1;node>=1;node>>=1) {

		seg[node]=max(seg[node<<1],seg[(node<<1)|1]);

	}

}

void build(int node,int bas,int son,int Y[]) {

	if(bas==son) {

		seg[node]=Y[bas];
		tut[bas]=node;

		return ;

	}

	build(node*2,bas,orta,Y);
	build(node*2+1,orta+1,son,Y);

	seg[node]=max(seg[node*2],seg[node*2+1]);

}

int get_ans() {

	vector< ii > v;

	int tot=0;

	auto it=S.end();

	it--;

	while(tot++<1000) {

		v.pb({it->xpro,it->mxy});

//		printf("%dth xpro-->%d mxy-->%d\n",tot-1,v.back().st,v.back().nd);

		if(it==S.begin()) break ;

		it--;

	}

	reverse(all(v));

	int best_ind=0;

	for(int i=0;i<tot;i++) {

		int ind=i;
		ll curpro=1;

		while(i+1<tot) {

			ll val=1ll*v[i+1].st*v[i+1].nd;

			if(val<v[ind].nd && curpro*val<v[ind].nd) {

				curpro*=v[i+1].st;

				i++;

				continue ;

			}

			break ;

		}

		if(i==tot-1) {

			best_ind=ind;

			break ;

		}

	}

	int dv=1;

	for(int i=tot-1;i>best_ind;i--) {

		dv=1ll*dv*v[i].st%MOD;

	}

	return 1ll*fe(dv,MOD-2)*allpro%MOD*v[best_ind].nd%MOD;

}

int init(int N, int X[], int Y[]) {
	
	::N=N;

	for(int i=0;i<N;i++) {

		::X[i]=X[i];

		day cur(i,i,X[i],Y[i]);

		while(i+1<N && X[i+1]==1) {

			i++;

			cur.r=i;
			cur.mxy=max(cur.mxy,Y[i]);

			::X[i]=X[i];

		}

		S.insert(cur);

		allpro=1ll*allpro*cur.xpro%MOD;

	}

	build(1,0,N-1,Y);

	return get_ans();

}

int updateX(int pos, int val) {	
	
	allpro=1ll*allpro*fe(X[pos],MOD-2)%MOD;

	allpro=1ll*allpro*val%MOD;

	if(X[pos]==1 && val!=1) {

		day cur(pos,pos,0,0);

		auto _pos=S.lower_bound(cur);

		cur=*_pos;

		S.erase(_pos);

		day l(cur.l,pos-1,cur.xpro,get(1,0,N-1,cur.l,pos-1));
		day r(pos,cur.r,val,get(1,0,N-1,pos,cur.r));

		S.insert(l);
		S.insert(r);

	}

	if(X[pos]>1 && val==1) {

		day cur(pos,pos,0,0);

		auto _pos=S.lower_bound(cur);

		if(_pos==S.begin()) {

			cur=*_pos;

			S.erase(_pos);

			cur.xpro=1;

			S.insert(cur);

		}
		else {

			day cur2=*_pos;

			S.erase(_pos--);

			day cur1=*_pos;

			S.erase(_pos);

			day nw(cur1.l,cur2.r,cur1.xpro,max(cur1.mxy,cur2.mxy));

			S.insert(nw);

		}

	}

	if(X[pos]>1 && val>1) {

		day cur(pos,pos,0,0);

		auto _pos=S.lower_bound(cur);

		cur=*_pos;

		S.erase(_pos);

		cur.xpro=val;

		S.insert(cur);

	}

	X[pos]=val;

	return get_ans();

}

int updateY(int pos, int val) {
	
	up(pos,val);

	day cur(pos,pos,0,0);

	auto _pos=S.lower_bound(cur);

	cur=*_pos;

	S.erase(_pos);

	cur.mxy=get(1,0,N-1,cur.l,cur.r);

	S.insert(cur);

	return get_ans();

}

Compilation message

horses.cpp: In function 'int fe(int, int)':
horses.cpp:53:26: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   if(y&1) res=1ll*res*cur%MOD;
                          ^
horses.cpp:57:18: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   cur=1ll*cur*cur%MOD;
                  ^
horses.cpp: In function 'int get_ans()':
horses.cpp:168:20: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   dv=1ll*dv*v[i].st%MOD;
                    ^
horses.cpp:172:51: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return 1ll*fe(dv,MOD-2)*allpro%MOD*v[best_ind].nd%MOD;
                                                   ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:176:33: warning: declaration of 'X' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:42:5: note: shadowed declaration is here
 int X[500005];
     ^
horses.cpp:176:33: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:41:5: note: shadowed declaration is here
 int N;
     ^
horses.cpp:199:29: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   allpro=1ll*allpro*cur.xpro%MOD;
                             ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:211:36: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  allpro=1ll*allpro*fe(X[pos],MOD-2)%MOD;
                                    ^
horses.cpp:213:23: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  allpro=1ll*allpro*val%MOD;
                       ^
horses.cpp: In function 'int get(int, int, int, int, int)':
horses.cpp:73:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 444 KB Output is correct
4 Correct 3 ms 644 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 3 ms 744 KB Output is correct
8 Correct 3 ms 744 KB Output is correct
9 Correct 3 ms 744 KB Output is correct
10 Correct 2 ms 744 KB Output is correct
11 Correct 3 ms 744 KB Output is correct
12 Correct 3 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 2 ms 744 KB Output is correct
18 Correct 2 ms 744 KB Output is correct
19 Correct 3 ms 744 KB Output is correct
20 Correct 3 ms 744 KB Output is correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 744 KB Output is correct
2 Correct 3 ms 744 KB Output is correct
3 Correct 3 ms 744 KB Output is correct
4 Correct 2 ms 744 KB Output is correct
5 Correct 2 ms 744 KB Output is correct
6 Correct 3 ms 744 KB Output is correct
7 Correct 3 ms 744 KB Output is correct
8 Correct 3 ms 744 KB Output is correct
9 Correct 2 ms 744 KB Output is correct
10 Correct 2 ms 744 KB Output is correct
11 Correct 3 ms 744 KB Output is correct
12 Correct 3 ms 744 KB Output is correct
13 Correct 2 ms 744 KB Output is correct
14 Correct 2 ms 744 KB Output is correct
15 Correct 2 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 3 ms 744 KB Output is correct
20 Correct 2 ms 744 KB Output is correct
21 Correct 2 ms 744 KB Output is correct
22 Correct 2 ms 744 KB Output is correct
23 Correct 8 ms 744 KB Output is correct
24 Correct 7 ms 744 KB Output is correct
25 Correct 26 ms 836 KB Output is correct
26 Execution timed out 1576 ms 880 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1564 ms 44360 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 44360 KB Output is correct
2 Correct 2 ms 44360 KB Output is correct
3 Correct 2 ms 44360 KB Output is correct
4 Correct 3 ms 44360 KB Output is correct
5 Correct 3 ms 44360 KB Output is correct
6 Correct 3 ms 44360 KB Output is correct
7 Correct 2 ms 44360 KB Output is correct
8 Correct 2 ms 44360 KB Output is correct
9 Correct 2 ms 44360 KB Output is correct
10 Correct 3 ms 44360 KB Output is correct
11 Correct 3 ms 44360 KB Output is correct
12 Correct 2 ms 44360 KB Output is correct
13 Correct 2 ms 44360 KB Output is correct
14 Correct 2 ms 44360 KB Output is correct
15 Correct 3 ms 44360 KB Output is correct
16 Correct 2 ms 44360 KB Output is correct
17 Correct 3 ms 44360 KB Output is correct
18 Correct 3 ms 44360 KB Output is correct
19 Correct 2 ms 44360 KB Output is correct
20 Correct 2 ms 44360 KB Output is correct
21 Correct 3 ms 44360 KB Output is correct
22 Correct 3 ms 44360 KB Output is correct
23 Correct 8 ms 44360 KB Output is correct
24 Correct 7 ms 44360 KB Output is correct
25 Correct 22 ms 44360 KB Output is correct
26 Execution timed out 1551 ms 44360 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 44360 KB Output is correct
2 Correct 2 ms 44360 KB Output is correct
3 Correct 2 ms 44360 KB Output is correct
4 Correct 3 ms 44360 KB Output is correct
5 Correct 2 ms 44360 KB Output is correct
6 Correct 4 ms 44360 KB Output is correct
7 Correct 2 ms 44360 KB Output is correct
8 Correct 3 ms 44360 KB Output is correct
9 Correct 2 ms 44360 KB Output is correct
10 Correct 3 ms 44360 KB Output is correct
11 Correct 3 ms 44360 KB Output is correct
12 Correct 2 ms 44360 KB Output is correct
13 Correct 2 ms 44360 KB Output is correct
14 Correct 3 ms 44360 KB Output is correct
15 Correct 3 ms 44360 KB Output is correct
16 Correct 3 ms 44360 KB Output is correct
17 Correct 3 ms 44360 KB Output is correct
18 Correct 2 ms 44360 KB Output is correct
19 Correct 2 ms 44360 KB Output is correct
20 Correct 3 ms 44360 KB Output is correct
21 Correct 3 ms 44360 KB Output is correct
22 Correct 3 ms 44360 KB Output is correct
23 Correct 7 ms 44360 KB Output is correct
24 Correct 10 ms 44360 KB Output is correct
25 Correct 22 ms 44360 KB Output is correct
26 Execution timed out 1573 ms 44360 KB Time limit exceeded
27 Halted 0 ms 0 KB -