Submission #26218

#	Time	Username	Problem	Language	Result	Execution time	Memory
26218		imsifile	Abduction 2 (JOI17_abduction2)	C++98	100 / 100	1393 ms	128528 KiB

abduction2

#include<stdio.h>
#include<memory.h>
#include<algorithm>
#include<map>
using namespace std;

typedef long long lld;

struct seg {
	lld j2, itr[150000];
	seg(){ j2 = 1<<16; memset(itr, 0x3f, sizeof(itr)); }
	const lld& operator[] (const lld ix){ return itr[j2+ix]; }
	void add(lld ix, lld val){
		ix+=j2; itr[ix]=val;
		for(ix>>=1; ix; ix>>=1) itr[ix]=max(itr[ix*2],itr[ix*2+1]);
	}
	lld getup(lld ix, lld val){
		ix+=j2;
		while(1){
			if(itr[ix]>val){
				if(ix>=j2) break;
				if(itr[ix*2]>val) ix*=2;
				else ix*=2, ix++;
			}
			else{
				if(ix%2) ix++;
				else ix>>=1;
			}
		}
		return ix-j2;
	}
	lld getdown(lld ix, lld val){
		ix+=j2;
		while(1){
			if(itr[ix]>val){
				if(ix>=j2) break;
				if(itr[ix*2+1]>val) ix*=2, ix++;
				else ix*=2;
			}
			else{
				if(ix%2 == 0) ix--;
				else ix>>=1;
			}
		}
		return ix-j2;
	}
} ho, ver;

lld H, W, Q;
map<pair<lld,lld>, lld> vd, hd;

lld verti(lld, lld);
lld hori(lld, lld);

lld verti(lld h, lld v){
	lld gap = vd[make_pair(h,v)];
	if(gap) return gap;

	lld up=0, down=0;
	up = ho.getup(h+1, ver[v]);
	if(up<=H) up = up-h + hori(v, up);
	else up = H-h;
	down = ho.getdown(h-1, ver[v]);
	if(down>=1) down = h-down + hori(v, down);
	else down = h-1;
	return vd[make_pair(h,v)] = max(up, down);
}

lld hori(lld v, lld h){
	lld gap = hd[make_pair(h,v)];
	if(gap) return gap;

	lld up=0, down=0;
	up = ver.getup(v+1, ho[h]);
	if(up<=W) up = up-v + verti(h, up);
	else up = W-v;
	down = ver.getdown(v-1, ho[h]);
	if(down>=1) down = v-down + verti(h, down);
	else down = v-1;

	return hd[make_pair(h,v)] = max(up, down);
}

int main(){
	scanf("%lld%lld%lld", &H, &W, &Q);
	for(lld i=1; i<=H; i++){
		lld a; scanf("%d", &a);
		ho.add(i, a);
	}
	for(lld i=1; i<=W; i++){
		lld a; scanf("%lld", &a);
		ver.add(i, a);
	}
	while(Q--){
		lld h, v;
		scanf("%lld%lld", &h, &v);
		printf("%lld\n", max(verti(h, v), hori(v, h)));
	}
	return 0;
}

Compilation message (stderr)

abduction2.cpp: In function 'int main()':
abduction2.cpp:87:24: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'lld* {aka long long int*}' [-Wformat=]
   lld a; scanf("%d", &a);
                        ^
abduction2.cpp:85:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld", &H, &W, &Q);
                                   ^
abduction2.cpp:87:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   lld a; scanf("%d", &a);
                         ^
abduction2.cpp:91:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   lld a; scanf("%lld", &a);
                           ^
abduction2.cpp:96:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &h, &v);
                            ^

• Subtask 1: 13 / 13
• Subtask 2: 10 / 10
• Subtask 3: 17 / 17
• Subtask 4: 4 / 4
• Subtask 5: 56 / 56