oj.uz

Submission #142535

# Submission time Handle Problem Language Result Execution time Memory
142535 2019-08-09T11:37:09 Z cheetose 버스 (JOI14_bus) C++11
100 / 100
 839 ms 60664 KB 
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#include<string>
#include<stack>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<complex>
#include<cmath>
#include<iomanip>
#include<numeric>
#include<algorithm>
#include<list>
#include<functional>
#include<cassert>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define y0 y12
#define y1 y22
#define INF 987654321
#define PI 3.141592653589793238462643383279502884
#define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c))
#define MEM0(a) memset((a),0,sizeof(a));
#define MEM_1(a) memset((a),-1,sizeof(a));
#define ALL(a) a.begin(),a.end()
#define SYNC ios_base::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<ld, ld> Pd;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<double> Vd;
typedef vector<Pi> VPi;
typedef vector<Pll> VPll;
typedef vector<Pd> VPd;
typedef tuple<int, int, int> iii;
typedef tuple<int,int,int,int> iiii;
typedef tuple<ll, ll, ll> LLL;
typedef vector<iii> Viii;
typedef vector<LLL> VLLL;
typedef complex<double> base;
const ll MOD = 1000000007;
ll POW(ll a, ll b, ll MMM = MOD) {ll ret=1; for(;b;b>>=1,a=(a*a)%MMM)if(b&1)ret=(ret*a)% MMM; return ret; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { if (a == 0 || b == 0)return a + b; return a*(b / gcd(a, b)); }
int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 };

int n,m;
Vi vv[100001];
int a[300000],b[300000],x[300000],y[300000];
VPi t;
Vi v[600000];
int d[600000];
int go(int N)
{
	if(t[N].X==1)return t[N].Y;
	int &ret=d[N];
	if(ret!=-INF-5)return ret;
	ret=-1;
	for(int next:v[N])ret=max(ret,go(next));
	return ret;
}
int main() {
	fill(d,d+600000,-INF-5);
	scanf("%d%d",&n,&m);
	fup(i,0,m-1,1)
	{
		scanf("%d%d%d%d",a+i,b+i,x+i,y+i);
		vv[a[i]].pb(x[i]);
		vv[b[i]].pb(y[i]);
	}
	fup(i,1,n,1)
	{
		sort(ALL(vv[i]));
		for(int j:vv[i])t.pb(mp(i,j));
	}
	int N=t.size();
	int L=-1,R=N-1;
	fup(i,1,N-1,1)
	{
		if(t[i].X==t[i-1].X)v[i].pb(i-1);
		if(t[i].X==n && L==-1)L=i;
	}
	if(L==-1)
	{
		int q;
		scanf("%d",&q);
		while(q--)puts("-1");
		return 0;
	}
	fup(i,0,m-1,1)
	{
		int t1=lower_bound(ALL(t),mp(b[i],y[i]))-t.begin();
		int t2=lower_bound(ALL(t),mp(a[i],x[i]))-t.begin();
		v[t1].pb(t2);
	}
	int q;
	scanf("%d",&q);
	while(q--)
	{
		int xx;
		scanf("%d",&xx);
		int l=L,r=R;
		while(l<=r)
		{
			int k=(l+r)>>1;
			if(t[k].Y<=xx)l=k+1;
			else r=k-1;
		}
		if(r==L-1)puts("-1");
		else printf("%d\n",go(r));
	}
}

Compilation message

bus.cpp: In function 'int main()':
bus.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
bus.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d",a+i,b+i,x+i,y+i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bus.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&q);
   ~~~~~^~~~~~~~~
bus.cpp:113:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
bus.cpp:117:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&xx);
   ~~~~~^~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19192 KB Output is correct
2 Correct 19 ms 19192 KB Output is correct
3 Correct 19 ms 19192 KB Output is correct
4 Correct 20 ms 19208 KB Output is correct
5 Correct 19 ms 19192 KB Output is correct
6 Correct 19 ms 19192 KB Output is correct
7 Correct 19 ms 19164 KB Output is correct
8 Correct 19 ms 19192 KB Output is correct
9 Correct 19 ms 19192 KB Output is correct
10 Correct 19 ms 19196 KB Output is correct
11 Correct 21 ms 19448 KB Output is correct
12 Correct 21 ms 19448 KB Output is correct
13 Correct 21 ms 19568 KB Output is correct
14 Correct 22 ms 19448 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 19320 KB Output is correct
2 Correct 55 ms 20892 KB Output is correct
3 Correct 54 ms 20856 KB Output is correct
4 Correct 32 ms 19320 KB Output is correct
5 Correct 23 ms 19320 KB Output is correct
6 Correct 22 ms 19192 KB Output is correct
7 Correct 44 ms 19704 KB Output is correct
8 Correct 19 ms 19192 KB Output is correct
9 Correct 39 ms 19832 KB Output is correct
10 Correct 58 ms 20944 KB Output is correct
11 Correct 42 ms 20216 KB Output is correct
12 Correct 61 ms 21244 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 670 ms 58448 KB Output is correct
2 Correct 665 ms 58396 KB Output is correct
3 Correct 689 ms 58448 KB Output is correct
4 Correct 661 ms 58436 KB Output is correct
5 Correct 655 ms 58308 KB Output is correct
6 Correct 661 ms 58396 KB Output is correct
7 Correct 633 ms 58600 KB Output is correct
8 Correct 679 ms 58500 KB Output is correct
9 Correct 751 ms 58516 KB Output is correct
10 Correct 620 ms 58684 KB Output is correct
11 Correct 601 ms 58908 KB Output is correct
12 Correct 647 ms 58820 KB Output is correct
13 Correct 639 ms 58848 KB Output is correct
14 Correct 638 ms 58848 KB Output is correct
15 Correct 630 ms 58820 KB Output is correct
16 Correct 212 ms 40300 KB Output is correct
17 Correct 171 ms 34144 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 717 ms 59896 KB Output is correct
2 Correct 719 ms 59516 KB Output is correct
3 Correct 839 ms 59956 KB Output is correct
4 Correct 727 ms 60072 KB Output is correct
5 Correct 690 ms 59572 KB Output is correct
6 Correct 693 ms 59796 KB Output is correct
7 Correct 695 ms 60296 KB Output is correct
8 Correct 822 ms 59952 KB Output is correct
9 Correct 715 ms 59976 KB Output is correct
10 Correct 837 ms 60456 KB Output is correct
11 Correct 740 ms 60472 KB Output is correct
12 Correct 716 ms 60664 KB Output is correct
13 Correct 680 ms 60464 KB Output is correct
14 Correct 764 ms 60508 KB Output is correct
15 Correct 702 ms 60656 KB Output is correct
16 Correct 232 ms 41336 KB Output is correct