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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;

void solve() {
    int n;
    string s,tmp="";
    cin>>n>>s;
    for(int i=0;i<n;i++){
        if(s[i]>='0'&&s[i]<='9'){
            tmp+=s[i];
        }
        else break;
    }
    if (!tmp.empty()) {
        for (int i = 0; i < tmp.size() - 1; i++) {
            if (tmp[i] > tmp[i + 1]) {
                cout << "NO\n";
                return;
            }
        }
    }

    for(int i=tmp.size();i<n-1;i++){
        if(s[i]>='0'&&s[i]<='9'){
            cout<<"NO\n";
            return;
        }
        if(s[i]>s[i+1]){
            cout<<"NO\n";
            return;
        }
    }
    cout<<"YES\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

 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
31
32
33
34
35
36

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;

void solve() {
    int n;
    cin>>n;
    vector<ll>a(n),b(n+1);
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<=n;i++)cin>>b[i];
    ll ans=0,tmp=1e9,t=0;
    for(int i=0;i<n;i++){
        ans+=abs(a[i]-b[i]);
        if(a[i]>=b[n]&&a[i]>=b[i]&&b[n]>=b[i])t=1;
        else if(a[i]<=b[n]&&a[i]<=b[i]&&b[n]<=b[i])t=1;
        else{
            int ta=abs(b[n]-min(a[i],b[i]))+1;
            int tb=abs(b[n]-max(a[i],b[i]))+1;
            t=min(ta,tb);
        }
        tmp=min(tmp,t);
    }
    ans+=tmp;
    cout<<ans<<"\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include <bits/stdc++.h>
using namespace std;
#define ls now << 1
#define rs now << 1 | 1
#define endl "\n"
#define lowbit(x) ((x) & (-x))
#define int long long
typedef long long ll;
const int N = 2e5 + 7, mod = 1e9 + 7;

int n, m;
int a[N * 2], b[N * 2], pre[N * 2];
ll ans[N * 2], sum[N * 2], sa[N * 2], sb[N * 2];

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n + m + 1; i++) cin >> a[i];
    for (int i = 1; i <= n + m + 1; i++) cin >> b[i];
    for (int i = 1; i <= n + m + 1; i++) pre[i] = pre[i - 1] + (a[i] > b[i]);
    for (int i = 1; i <= n + m + 1; i++) sum[i] = sum[i - 1] + max(a[i], b[i]);
    sa[n + m + 2] = sb[n + m + 2] = 0;
    for (int i = n + m + 1; i > 0; i--) {
        sa[i] = sa[i + 1] + a[i];
        sb[i] = sb[i + 1] + b[i];
    }
    for (int i = 1; i <= n + m + 1; i++) {
        int l = 0, r = n + m + 1, ans = -1;
        ll NA, NB;
        while (l <= r) {
            ll mid = (l + r) >> 1;
            int na = pre[mid], nb = mid - na;
            if (mid >= i) (a[i] > b[i] ? na : nb)--;
            if (na >= n || nb >= m) {
                NA = na, NB = nb;
                r = mid - 1, ans = mid;
            } else
                l = mid + 1;
        }
        int res = sum[ans] - (ans >= i ? max(a[i], b[i]) : 0ll);
        res += NB == m ? sa[ans + 1] - (ans + 1 <= i ? a[i] : 0) : sb[ans + 1] - (ans + 1 <= i ? b[i] : 0);
        cout << res << " ";
    }
    cout << endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}