제출 #533290

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
533290		arnold518	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	871 ms	67648 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int INF = 1e9;

int N, M, K;
pii A[MAXN+10];

pii operator + (const pii &p, const pii &q) { return {min(p.first, q.first), max(p.second, q.second)}; }

struct SEG
{
	pii tree[MAXN*4+10];

	void init(int node, int tl, int tr)
	{
		if(tl==tr)
		{
			tree[node]={tl, tl};
			return;
		}
		int mid=tl+tr>>1;
		init(node*2, tl, mid);
		init(node*2+1, mid+1, tr);
		tree[node]={INF, -INF};
	}

	void update(int node, int tl, int tr, int l, int r, pii k)
	{
		if(r<tl || tr<l) return;
		if(l<=tl && tr<=r)
		{
			tree[node]=tree[node]+k;
			return;
		}
		int mid=tl+tr>>1;
		update(node*2, tl, mid, l, r, k);
		update(node*2+1, mid+1, tr, l, r, k);
	}	

	void query(int node, int tl, int tr, pii t)
	{
		t.first=min(t.first, tree[node].first);
		t.second=max(t.second, tree[node].second);
		if(tl==tr)
		{
			A[tl]=t;
			return;
		}
		int mid=tl+tr>>1;
		query(node*2, tl, mid, t);
		query(node*2+1, mid+1, tr, t);
	}
}seg;

struct SEG2
{
	pii tree[MAXN*4+10][30];
	
	pii query(int node, int tl, int tr, int l, int r, int k)
	{
		if(l<=tl && tr<=r) return tree[node][k];
		if(r<tl || tr<l) return {INF, -INF};
		int mid=tl+tr>>1;
		return query(node*2, tl, mid, l, r, k)+query(node*2+1, mid+1, tr, l, r, k);
	}

	void flush(int node, int tl, int tr, int k)
	{
		if(tl==tr)
		{
			tree[node][k]=A[tl];
			return;
		}
		int mid=tl+tr>>1;
		flush(node*2, tl, mid, k);
		flush(node*2+1, mid+1, tr, k);
		tree[node][k]=tree[node*2][k]+tree[node*2+1][k];
	}

	void init()
	{
		flush(1, 1, N, 0);
		for(int i=1; i<=20; i++)
		{
			for(int j=1; j<=N; j++)	A[j]=query(1, 1, N, A[j].first, A[j].second, i-1);
			flush(1, 1, N, i);
		}
	}
}seg2;

int main()
{
	scanf("%d%d%d", &N, &K, &M);
	seg.init(1, 1, N);
	for(int i=1; i<=M; i++)
	{
		int l, r;
		scanf("%d%d", &l, &r);
		if(l<r)
		{
			seg.update(1, 1, N, l, min(l+K-1, r-1), {INF, r});
		}
		else
		{
			seg.update(1, 1, N, max(l-K+1, r+1), l, {r, -INF});
		}
	}
	seg.query(1, 1, N, {INF, -INF});
	seg2.init();

	scanf("%d", &M);
	while(M--)
	{
		int s, e;
		scanf("%d%d", &s, &e);
		pii t=seg2.query(1, 1, N, s, s, 20);
		if(t.first>e || t.second<e) { printf("-1\n"); continue; }

		int ans=0, l=s, r=s;
		for(int i=19; i>=0; i--)
		{
			pii t=seg2.query(1, 1, N, l, r, i);
			if(t.first>e || t.second<e)
			{
				ans|=(1<<i);
				l=t.first; r=t.second;
			}
		}
		printf("%d\n", ans+1);
	}
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In member function 'void SEG::init(int, int, int)':
Main.cpp:27:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |   int mid=tl+tr>>1;
      |           ~~^~~
Main.cpp: In member function 'void SEG::update(int, int, int, int, int, pii)':
Main.cpp:41:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |   int mid=tl+tr>>1;
      |           ~~^~~
Main.cpp: In member function 'void SEG::query(int, int, int, pii)':
Main.cpp:55:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |   int mid=tl+tr>>1;
      |           ~~^~~
Main.cpp: In member function 'pii SEG2::query(int, int, int, int, int, int)':
Main.cpp:69:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |   int mid=tl+tr>>1;
      |           ~~^~~
Main.cpp: In member function 'void SEG2::flush(int, int, int, int)':
Main.cpp:80:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |   int mid=tl+tr>>1;
      |           ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:99:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |  scanf("%d%d%d", &N, &K, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |   scanf("%d%d", &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:117:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |  scanf("%d", &M);
      |  ~~~~~^~~~~~~~~~
Main.cpp:121:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |   scanf("%d%d", &s, &e);
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 13 / 13