답안 #98075 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
98075	2019-02-20T13:51:08 Z	dndhk	Worst Reporter 2 (JOI16_worst_reporter2)	C++14	30 / 100	2000 ms	5768 KB

worst_reporter2

#include <bits/stdc++.h>

#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL


using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 200000;
int N;
vector<pii> v1, v2;
int idx[MAX_N+1];
vector<int> g[MAX_N+1];
int cnt[MAX_N+1];
int chk[MAX_N+1];
int ans;

bool match(int x, int y){
	int t = 0;
	for(int i = 0; i<x; i++){
		if(chk[i])	continue;
		t++;
		if(idx[i]>=y){
			int sum = 0;
			for(int j=0; j<=idx[i]; j++){
				sum+=cnt[j];
			}
			if(sum<=t)	return false;
		}
	}return true;
}

int main(){
	scanf("%d", &N);	for(int i=0; i<N; i++)	cnt[i]++;
	ans = N;
	for(int i=0 ;i<N; i++){
		int a, b; scanf("%d%d", &a, &b);
		v1.push_back({a, b});
	}for(int i=0; i<N; i++){
		int a, b; scanf("%d%d", &a, &b);
		v2.push_back({a, b});
	}
	for(int i=0; i<N; i++){
		if(i==0)	idx[i] = 0;
		else	idx[i] = idx[i-1];
		while(idx[i]!=N-1 && v2[idx[i]+1].SE >= v1[i].SE){
			idx[i]++;
		}
	}
	int index = 0;
	for(int i=0; i<N; i++){
		while(index<N && v2[index].SE >= v1[i].SE){
			g[v2[index].FI].push_back(index); index++;
		}   
		if(!g[v1[i].FI].empty()){
			int k = g[v1[i].FI].back();
			//cout<<i<<' '<<k<<endl;
			if(match(i, k)){
				//cout<<i<<' '<<k<<endl;
				cnt[k]--; chk[i] = true; ans--;
				g[v1[i].FI].pop_back();
			}
		}
	}
	printf("%d", ans);
	return 0;
}

Compilation message

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N); for(int i=0; i<N; i++) cnt[i]++;
  ~~~~~^~~~~~~~~~
worst_reporter2.cpp:52:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d%d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~
worst_reporter2.cpp:55:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d%d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	4992 KB	Output is correct
2	Correct	5 ms	4992 KB	Output is correct
3	Correct	6 ms	4992 KB	Output is correct
4	Correct	7 ms	4992 KB	Output is correct
5	Correct	7 ms	4992 KB	Output is correct
6	Correct	6 ms	4992 KB	Output is correct
7	Correct	8 ms	5120 KB	Output is correct
8	Correct	8 ms	5120 KB	Output is correct
9	Correct	9 ms	5120 KB	Output is correct
10	Correct	8 ms	5164 KB	Output is correct
11	Correct	7 ms	4992 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	4992 KB	Output is correct
2	Correct	5 ms	4992 KB	Output is correct
3	Correct	6 ms	4992 KB	Output is correct
4	Correct	7 ms	4992 KB	Output is correct
5	Correct	7 ms	4992 KB	Output is correct
6	Correct	6 ms	4992 KB	Output is correct
7	Correct	8 ms	5120 KB	Output is correct
8	Correct	8 ms	5120 KB	Output is correct
9	Correct	9 ms	5120 KB	Output is correct
10	Correct	8 ms	5164 KB	Output is correct
11	Correct	7 ms	4992 KB	Output is correct
12	Correct	8 ms	5120 KB	Output is correct
13	Correct	6 ms	5120 KB	Output is correct
14	Correct	7 ms	4992 KB	Output is correct
15	Correct	8 ms	4992 KB	Output is correct
16	Correct	7 ms	5120 KB	Output is correct
17	Correct	7 ms	4992 KB	Output is correct
18	Correct	8 ms	5120 KB	Output is correct
19	Correct	8 ms	4992 KB	Output is correct
20	Correct	8 ms	5248 KB	Output is correct
21	Correct	7 ms	5120 KB	Output is correct
22	Correct	6 ms	4992 KB	Output is correct

Subtask #3
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	4992 KB	Output is correct
2	Correct	5 ms	4992 KB	Output is correct
3	Correct	6 ms	4992 KB	Output is correct
4	Correct	7 ms	4992 KB	Output is correct
5	Correct	7 ms	4992 KB	Output is correct
6	Correct	6 ms	4992 KB	Output is correct
7	Correct	8 ms	5120 KB	Output is correct
8	Correct	8 ms	5120 KB	Output is correct
9	Correct	9 ms	5120 KB	Output is correct
10	Correct	8 ms	5164 KB	Output is correct
11	Correct	7 ms	4992 KB	Output is correct
12	Correct	8 ms	5120 KB	Output is correct
13	Correct	6 ms	5120 KB	Output is correct
14	Correct	7 ms	4992 KB	Output is correct
15	Correct	8 ms	4992 KB	Output is correct
16	Correct	7 ms	5120 KB	Output is correct
17	Correct	7 ms	4992 KB	Output is correct
18	Correct	8 ms	5120 KB	Output is correct
19	Correct	8 ms	4992 KB	Output is correct
20	Correct	8 ms	5248 KB	Output is correct
21	Correct	7 ms	5120 KB	Output is correct
22	Correct	6 ms	4992 KB	Output is correct
23	Correct	459 ms	5532 KB	Output is correct
24	Correct	472 ms	5500 KB	Output is correct
25	Correct	449 ms	5768 KB	Output is correct
26	Correct	17 ms	5376 KB	Output is correct
27	Execution timed out	2008 ms	5376 KB	Time limit exceeded
28	Halted	0 ms	0 KB	-

Subtask #4
0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	4992 KB	Output is correct
2	Correct	5 ms	4992 KB	Output is correct
3	Correct	6 ms	4992 KB	Output is correct
4	Correct	7 ms	4992 KB	Output is correct
5	Correct	7 ms	4992 KB	Output is correct
6	Correct	6 ms	4992 KB	Output is correct
7	Correct	8 ms	5120 KB	Output is correct
8	Correct	8 ms	5120 KB	Output is correct
9	Correct	9 ms	5120 KB	Output is correct
10	Correct	8 ms	5164 KB	Output is correct
11	Correct	7 ms	4992 KB	Output is correct
12	Correct	8 ms	5120 KB	Output is correct
13	Correct	6 ms	5120 KB	Output is correct
14	Correct	7 ms	4992 KB	Output is correct
15	Correct	8 ms	4992 KB	Output is correct
16	Correct	7 ms	5120 KB	Output is correct
17	Correct	7 ms	4992 KB	Output is correct
18	Correct	8 ms	5120 KB	Output is correct
19	Correct	8 ms	4992 KB	Output is correct
20	Correct	8 ms	5248 KB	Output is correct
21	Correct	7 ms	5120 KB	Output is correct
22	Correct	6 ms	4992 KB	Output is correct
23	Correct	459 ms	5532 KB	Output is correct
24	Correct	472 ms	5500 KB	Output is correct
25	Correct	449 ms	5768 KB	Output is correct
26	Correct	17 ms	5376 KB	Output is correct
27	Execution timed out	2008 ms	5376 KB	Time limit exceeded
28	Halted	0 ms	0 KB	-

답안 #98075

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 15.0 / 15.0

Subtask #3 0 / 30.0

Subtask #4 0 / 40.0

Subtask #1
15.0 / 15.0

Subtask #2
15.0 / 15.0

Subtask #3
0 / 30.0

Subtask #4
0 / 40.0