QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#135717#6385. SwordsMohammed_Atalah#0 75ms19656kbC++172.1kb2023-08-05 23:13:382024-07-04 01:17:53

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 01:17:53]
  • 评测
  • 测评结果:0
  • 用时:75ms
  • 内存:19656kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-05 23:13:38]
  • 提交

answer

/// Template path: /home/mohammed/.config/sublime-text-3/Packages/User

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

// typedef
typedef long long ll;
typedef long double ld;
typedef vector<int> vecint;
typedef vector<char> vecchar;
typedef vector<string> vecstr;
typedef vector<long long> vecll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

// Marcos
#define endl ("\n")
#define int long long
#define mod 1000000007
#define pi (3.141592653589)
#define REP(i,a,b) for (int i = a; i < b; i++)
#define RREP(i,a,b) for (int i = a; i > b; i--)
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)

// Functions
long long squared(long long x) {return (x * x) % mod;}
int factorial(int n) {long long res = 1; for (int i = 1; i <= n; i++) {res = ((res * i) % mod + mod) % mod ;} return res;}
long long power(long long x, long long p) {if (p == 0) {return 1;} if (p % 2 == 1) {return (power(x, p - 1) * x) % mod;} return squared(power(x, p / 2));}

// cout << fixed;
// cout << setprecision(4);


// ---------(^_^)--------- //




void main_solve() {


	int n; cin >> n;
	map<int, int> mp;
	vector<vector<int>>v;
	set<int> w;
	for (int i  = 0; i < n ; i++) {
		int a, b; cin >> a >> b;
		w.insert(a);
		v.push_back({a, b});
	}
	sort(v.begin(), v.end());

	int mx = 0;
	for (int i  = n - 1; i >= 0; i--) {
		mx = max(v[i][1], mx);
		mp[v[i][0]] = mx;
	}
	int result = 0;
	for (int i = 0; i < n ; i ++) {
		if (mp[v[i][0]] <= v[i][1]) {
			auto it = w.upper_bound(v[i][0]);
			if ((it != w.end() && mp[*it] <= v[i][1]) || i == n - 1) {
				result++;
			}
		}
	}

	cout << result << endl;

}


int32_t main() {

	fast;
// #ifndef ONLINE_JUDGE
// 	freopen("input.txt", "r", stdin);
// 	freopen("output.txt", "w", stdout);
// #endif
	// Just another problem (-_-)

	int t;
	t = 1;
	// cin >> t;

	while (t--) {
		main_solve();
	}


}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 11
Accepted
time: 0ms
memory: 3624kb

input:

1
963837006 731841442

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

2
948507270 461613425
139535653 575270914

output:

2

result:

ok single line: '2'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

10
319645572 758298525
812547177 459359946
355467212 304450522
807957797 916787906
239781206 242840396
862552539 873867121
975802175 647540462
425058513 132645393
542726039 946723283
689442435 88379179

output:

4

result:

ok single line: '4'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3708kb

input:

500
324871127 81437847
409475382 449147781
489822349 623579845
541818045 840744984
661020437 969739509
798121975 645320144
816860092 800579487
824869844 529655705
465683506 749124928
598994662 884712609
209267210 57701594
429537250 605036253
621863743 894173810
124365859 688557442
292413610 13087016...

output:

6

result:

ok single line: '6'

Test #5:

score: -11
Wrong Answer
time: 1ms
memory: 3704kb

input:

500
683386324 317939718
208613330 798920975
579714620 453381531
345595104 665823464
800877748 211763934
789188460 220973054
588560958 451627488
959388230 76567736
313310279 714219110
533824766 510880778
6504202 999158405
909358811 119409841
889857953 140960955
862319883 173370354
568240503 463420167...

output:

442

result:

wrong answer 1st lines differ - expected: '395', found: '442'

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 2ms
memory: 4072kb

input:

5000
335 370
93 303
246 51
165 259
316 29
272 282
43 25
475 268
124 326
10 161
268 309
351 349
8 130
16 313
381 433
133 293
176 154
84 213
323 315
244 180
18 368
177 184
452 122
233 128
151 337
409 419
487 500
62 440
484 333
489 245
331 62
272 218
22 481
234 89
93 188
123 312
57 278
129 152
496 437
...

output:

12

result:

wrong answer 1st lines differ - expected: '5', found: '12'

Subtask #3:

score: 0
Wrong Answer

Test #15:

score: 34
Accepted
time: 1ms
memory: 3792kb

input:

1000
1 999364420
2 998447750
3 998101971
4 997565306
5 997218128
6 996453842
7 996346759
8 991821522
9 991345816
10 991124285
11 989916443
12 989465292
13 988065411
14 987961309
15 986603323
16 986161187
17 984463465
18 983735350
19 982870592
20 981837956
21 979637953
22 979158794
23 977305448
24 97...

output:

943

result:

ok single line: '943'

Test #16:

score: 0
Accepted
time: 44ms
memory: 19656kb

input:

100000
1 35016634
2 42570102
3 347690764
4 483516799
5 999979181
6 1
7 2
8 3
9 10
10 40
11 137
12 235
13 357
14 548
15 3550
16 4870
17 11918
18 16779
19 5106657
20 10114779
21 137389249
22 335861312
23 999827272
24 1
25 6
26 7
27 9
28 37
29 38
30 48
31 63
32 74
33 91
34 1711
35 5585
36 13633
37 3558...

output:

4744

result:

ok single line: '4744'

Test #17:

score: -34
Wrong Answer
time: 75ms
memory: 19400kb

input:

100000
1 999989351
2 999976087
3 999973310
4 999960176
5 999955133
6 999945409
7 999933763
8 999902669
9 999902401
10 999895604
11 999880436
12 999876699
13 999860487
14 999854211
15 999842500
16 713698866
17 999818348
18 999812344
19 999811697
20 999785649
21 999782175
22 999772263
23 999770919
24 ...

output:

97641

result:

wrong answer 1st lines differ - expected: '97638', found: '97641'

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%