답안 #20198

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
20198	2016-03-13T00:55:42 Z	HIR180	말 (IOI15_horses)	C++	컴파일 오류	0 ms	0 KB

horses

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define fi first
#define sc second
#define pb push_back
#define mod 1000000007
set<pair<int,ll> >S;
typedef pair<pair<int,int>,ll> Q;
int n,m;
ll x[500005],y[500005];
ll seg[(1<<20)];
ll bit[(1<<20)];
void upd(int i,int x){
	for(int j=i;j<=n;j+=j&-j){
		bit[j] = bit[j]*x%mod;
	}
}
ll mul(int i){
	ll r = 1;
	for(int j=i;j>0;j-=j&-j){
		r = r*bit[j]%mod;
	}
	return r;
}
ll query(int a,int b,int k,int l,int r){
	if(r<a || b<l) return 0;
	if(a<=l && r<=b) return seg[k];
	return max(query(a,b,k*2+1,l,(l+r)/2),query(a,b,k*2+2,(l+r)/2+1,r));
}
void update(int i,int x){
	i += (1<<19)-1;
	seg[i] = x;
	while(i>0){
		i = (i-1)/2;
		seg[i] = max(seg[i*2+1],seg[i*2+2]);
	}
}
ll modpow(ll x,ll n){
	ll r = 1;
	for(int i=0;i<30;i++){
		if(((n>>i)&1)){
			r = r*x%mod;
		}
		x = x*x%mod;
	}
	return r;
}
int main(){
	scanf("%d",&n);
	fill(bit,bit+(1<<20),1);
	for(int i=0;i<n;i++){
		scanf("%lld",&x[i]);
		if(x[i] > 1){
			S.insert(mp(i,x[i]));
		}
		upd(i+1,x[i]);
	}
	if(x[0] == 1) S.insert(mp(0,1));
	for(int i=0;i<n;i++){
		scanf("%lld",&y[i]);
		seg[i+(1<<19)-1] = y[i];
	}
	for(int i=(1<<19)-2;i>=0;i--) seg[i] = max(seg[i*2+1],seg[i*2+2]);
	scanf("%d",&m);
	for(int i=0;i<=m;i++){
		ll cur = 1;
		int pre = n;
		set<pair<int,ll> >::iterator it = S.end(); --it;
		vector<Q>vq;
		for(;;it--){
			int L = it->fi;
			ll val = it->sc;
			vq.pb(mp(mp(L,pre-1),val));
			pre = L;
			cur *= val;
			if(cur > mod || it == S.begin()) break;
		}
		reverse(vq.begin(),vq.end());
		ll lb = mul(pre+1);
		ll M = 1; cur = 1;
		for(int j=0;j<vq.size();j++){
			if(j) cur *= vq[j].sc;
			M = max(M,query(vq[j].fi.fi,vq[j].fi.sc,0,0,(1<<19)-1)*cur);
		}
		M%=mod;
		printf("%lld\n",lb*M%mod);
		if(i==m) break;
		int a,b,c; scanf("%d%d%d",&a,&b,&c);
		if(a == 1){
			upd(b+1,c*modpow(x[b],mod-2)%mod);
			if(b){
				if(x[b]==1){
					if(c==1);
					else{
						S.insert(mp(b,c));
					}
					x[b] = c;
				}
				else{
					set<pair<int,ll> >::iterator it = S.lower_bound(mp(b,x[b]));
					assert((*it) == mp(b,x[b]));
					S.erase(it);
					if(c==1);
					else S.insert(mp(b,c));
					x[b] = c;
				}
			}
			else{
				set<pair<int,ll> >::iterator it = S.lower_bound(mp(b,x[b]));
				assert((*it) == mp(b,x[b]));
				S.erase(it);
				S.insert(mp(b,c));
				x[b] = c;
			}
		}
		else{
			update(b,c);
		}
	}
}

Compilation message

horses.cpp: In function 'void upd(int, int)':
horses.cpp:15:21: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 void upd(int i,int x){
                     ^
horses.cpp:12:4: note: shadowed declaration is here
 ll x[500005],y[500005];
    ^
horses.cpp: In function 'void update(int, int)':
horses.cpp:32:24: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 void update(int i,int x){
                        ^
horses.cpp:12:4: note: shadowed declaration is here
 ll x[500005],y[500005];
    ^
horses.cpp: In function 'll modpow(ll, ll)':
horses.cpp:40:20: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 ll modpow(ll x,ll n){
                    ^
horses.cpp:11:5: note: shadowed declaration is here
 int n,m;
     ^
horses.cpp:40:20: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 ll modpow(ll x,ll n){
                    ^
horses.cpp:12:4: note: shadowed declaration is here
 ll x[500005],y[500005];
    ^
horses.cpp: In function 'int main()':
horses.cpp:58:15: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   upd(i+1,x[i]);
               ^
horses.cpp:83:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<vq.size();j++){
                ^
horses.cpp:92:36: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
    upd(b+1,c*modpow(x[b],mod-2)%mod);
                                    ^
horses.cpp:102:35: warning: declaration of 'it' shadows a previous local [-Wshadow]
      set<pair<int,ll> >::iterator it = S.lower_bound(mp(b,x[b]));
                                   ^
horses.cpp:70:32: note: shadowed declaration is here
   set<pair<int,ll> >::iterator it = S.end(); --it;
                                ^
horses.cpp:111:34: warning: declaration of 'it' shadows a previous local [-Wshadow]
     set<pair<int,ll> >::iterator it = S.lower_bound(mp(b,x[b]));
                                  ^
horses.cpp:70:32: note: shadowed declaration is here
   set<pair<int,ll> >::iterator it = S.end(); --it;
                                ^
horses.cpp:51:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
horses.cpp:54:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&x[i]);
                      ^
horses.cpp:62:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&y[i]);
                      ^
horses.cpp:66:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
                ^
horses.cpp:90:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a,b,c; scanf("%d%d%d",&a,&b,&c);
                                      ^
/tmp/ccyTytn5.o: In function `main':
grader.c:(.text.startup+0x0): multiple definition of `main'
/tmp/ccwrw6hn.o:horses.cpp:(.text.startup+0x0): first defined here
/tmp/ccyTytn5.o: In function `main':
grader.c:(.text.startup+0x282): undefined reference to `init(int, int*, int*)'
grader.c:(.text.startup+0x75e): undefined reference to `updateX(int, int)'
grader.c:(.text.startup+0xae1): undefined reference to `updateY(int, int)'
collect2: error: ld returned 1 exit status