Submission #1360166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1360166		rukashii	Stone Arranging 2 (JOI23_ho_t1)	C++20	100 / 100	237 ms	24144 KiB

Main

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

#define file                                \
    if (fopen("input.txt", "r"))            \
    {                                       \
        freopen("input.txt", "r", stdin);   \
        freopen("output.txt", "w", stdout); \
    }
#define int long long

void setIn(string s) { freopen(s.c_str(), "r", stdin); }
void setOut(string s) { freopen(s.c_str(), "w", stdout); }
void setIO(string s = "")
{
    if (s.size())
        setIn(s + ".inp"), setOut(s + ".out");
}

const int maxn = 2e5 + 2;

struct dsu
{
    int id, r, val, nLeft, nRight;
};

dsu lab[maxn];

int get(int u)
{
    return (lab[u].id == -1) ? (u) : (lab[u].id = get(lab[u].id));
}

void unite(int u, int v)
{
    // uu >= vv
    int uu = get(u), vv = get(v);

    if (uu == vv)
        return;

    lab[vv].id = uu;
    lab[vv].r = max(lab[vv].r, lab[uu].r);
    // if (lab[uu].val != lab[vv].val)
    // {
    //     if (lab[vv].nLeft != -1)
    //         lab[lab[vv].nLeft].nRight = lab[vv].nRight;
    //     if (lab[vv].nRight != -1)
    //         lab[lab[vv].nRight].nLeft = lab[vv].nLeft;
    // }
    // else
    // {
    //     lab[uu].nRight = max(lab[uu].nRight, lab[vv].nRight);
    //     lab[uu].nLeft = max(lab[uu].nLeft, lab[vv].nLeft);
    // }

    if (lab[uu].val != lab[vv].val)
    {
        int L = lab[vv].nLeft;
        int R = lab[vv].nRight;
        if (L != -1)
            lab[get(L)].nRight = R;
        if (R != -1)
            lab[get(R)].nLeft = L;
    }
    else
    {
        lab[uu].nLeft = min(lab[uu].nLeft, lab[vv].nLeft);
        lab[uu].nRight = max(lab[uu].nRight, lab[vv].nRight);
    }
}

void solve()
{
    memset(lab, -1, sizeof(lab));

    int n;
    cin >> n;

    vector<int> a(n + 2, 0);
    for (int i = 1; i <= n; i++)
        cin >> a[i], lab[i].r = i, lab[i].val = a[i];

    map<int, int> mp;
    //     vector<int> compressed;
    //     for (int i = 1; i <= n; i++)
    //         compressed.push_back(a[i]);

    //     sort(compressed.begin(), compressed.end());
    //     compressed.erase(unique(compressed.begin(), compressed.end()), compressed.end());

    //     for (int i = 0; i < compressed.size(); i++)
    //         mp[compressed[i]] = i + 1;
    //     f

    for (int i = 1; i <= n; i++)
    {
        if (mp.count(a[i]))
            lab[i].nLeft = mp[a[i]];

        mp[a[i]] = i;
    }
    mp.clear();

    for (int i = n; i >= 1; i--)
    {
        if (mp.count(a[i]))
            lab[i].nRight = mp[a[i]];

        mp[a[i]] = i;
    }
    // for (int i = 1; i <= n; i++)
    //     cout << l[i] << ' ' << r[i] << '\n';

    // cout << lab[get(1)].r << '\n';
    for (int i = 1; i <= n; i++)
    {
        if (lab[get(i)].nLeft > 0)
        {
            int j = lab[get(i)].nLeft;
            while (j < i)
            {
                int tmp = lab[get(j)].r + 1;

                unite(i, j);
                j = tmp;
            }
        }

        // for (int k = 1; k <= n; k++)
        //     cout << lab[get(k)].nLeft << ' ' << lab[get(k)].nRight << '\n';
        // for (int k = 1; k <= n; k++)
        //     cout << lab[get(k)].val << ' ';
        // cout << '\n';
    }

    // cout << n << '\n';
    for (int i = 1; i <= n; i++)
        cout << lab[get(i)].val << ' ';
}

signed main()
{
    // setIO();
    file;
    ios::sync_with_stdio(0);
    cin.tie(0);

    solve();
}

Compilation message (stderr)

Main.cpp: In function 'void setIn(std::string)':
Main.cpp:12:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | void setIn(string s) { freopen(s.c_str(), "r", stdin); }
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'void setOut(std::string)':
Main.cpp:13:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | void setOut(string s) { freopen(s.c_str(), "w", stdout); }
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:7:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |         freopen("input.txt", "r", stdin);   \
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:145:5: note: in expansion of macro 'file'
  145 |     file;
      |     ^~~~
Main.cpp:8:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |         freopen("output.txt", "w", stdout); \
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:145:5: note: in expansion of macro 'file'
  145 |     file;
      |     ^~~~

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40