Submission #1255540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255540		Sam_arvandi	Monochrome Points (JOI20_monochrome)	C++20	25 / 100	702 ms	61248 KiB

monochrome

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;;
typedef pair<int, int> pii;

#define FOR(i, j, n) for(int i = j; i<= n; i++)
#define ROF(i, n, j) for(int i = n; i>= j; i--)
#define pb push_back
#define S second
#define F first
#define IOS ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define G(i, j) get<j-1>(i)
#define print(i) cout << #i << ": " << i
#define mp make_pair
const int mn = 2000 + 10;
int a[2*mn];
int g1[mn], g2[mn], p[mn];
pii s[mn*2];

struct Seg_tree
{
        struct Node
        {
                int ted = 0;
        }node[mn*4];

        void init(int id, int L, int R)
        {
                node[id].ted = 0;
                if (L+1 == R) return;
                int mid = (L+R)/2;
                init(id*2, L, mid);
                init(id*2 + 1, mid, R);
        }

        void update(int id, int L, int R, int ind)
        {
                node[id].ted++;
                if (L+1 == R) return;
                int mid = (L+R)/2;
                if (ind >= mid) update(id*2 + 1, mid, R, ind);
                else update(id*2, L, mid, ind);
        }

        int get(int id, int L, int R, int l, int r)
        {
                if (L == l and R == r) return node[id].ted;
                int mid = (L+R)/2;
                if (l >= mid) return get(id*2 + 1, mid, R, l, r);
                else if (r <= mid) return get(id*2, L, mid, l, r);
                else return get(id*2, L, mid, l, mid) + get(id*2 + 1, mid, R, mid, r);
        }
}seg[mn];


signed main()
{
        IOS;
        int n;
        cin >> n;
        string s2;
        cin >> s2;
        int tmp1 = 0, tmp2 = 0;
        FOR(i, 0, 2*n-1)
        {
                if (s2[i] == 'B')
                {
                        g1[tmp1] = i;
                        a[i] = 1;
                        tmp1++;
                }
                else
                {
                        g2[tmp2] = i;
                        a[i] = 2;
                        tmp2++;
                }
        }
        int out = 0;
        FOR(d, 0, n-1)
        {
                int ans = 0;
                FOR(i, 0, n-1)
                {
                        s[i] = mp(min(g1[i], g2[(i+d)%n]), max(g1[i], g2[(i+d)%n]));
                }
                sort(s, s+n);
                FOR(i, 0, n-1)
                {
                        ans += seg[d].get(1, 1, 2*n+1, s[i].F+1, s[i].S+1);
                        seg[d].update(1, 1, 2*n+1, s[i].S+1);
                }
                out = max(out, ans);
        }

        cout << out;

        return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 21 / 21
• Subtask 3: 0 / 10
• Subtask 4: 0 / 65