Submission #947391

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
947391	2024-03-16 05:34:45	weakweakweak	Building 4 (JOI20_building4)	C++17	11 / 100	43 ms	12952 KiB

building4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//joisc怎麼也有水題阿
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fs first
#define sc second
int n, a[510000], b[510000];
pii dp[510000][2];
pii dead = {1000000, -1000000};
int main () {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n * 2; i++) cin >> a[i];
    for (int i = 1; i <= n * 2; i++) cin >> b[i];
    
    a[0] = b[0] = -1, dp[0][0] = dp[0][1] = {0, 0};
    for (int i = 1; i <= n * 2; i++) dp[i][0] = dp[i][1] = dead;
    for (int i = 1; i <= n * 2; i++) {
        {
            bool y0 = (a[i] >= a[i - 1]) and (dp[i - 1][0] != dead),    y1 = (a[i] >= b[i-1]) and (dp[i - 1][1] != dead); 
            if (y0 and y1) {
                dp[i][0] . fs = min(dp[i - 1][0].fs, dp[i - 1][1].fs) + 1;
                dp[i][0] . sc = max(dp[i - 1][0].sc, dp[i - 1][1].sc) + 1;
            }
            else if (y0) dp[i][0] = {dp[i - 1][0].fs + 1, dp[i - 1][0].sc + 1};
            else if (y1) dp[i][0] = {dp[i - 1][1].fs + 1, dp[i - 1][1].sc + 1};
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 11 / 11
• Subtask 2: 0 / 89