Submission #1133254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133254		Gray	popa (BOI18_popa)	C++20	61 / 100	31 ms	556 KiB

popa

#include <bits/stdc++.h>
#include "popa.h"
using namespace std;
#define ll int
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair

#define INF 2e18
#define MOD 1e9+7

struct Node{
    Node * left, * right; ll ind;
    Node(ll _ind):ind(_ind){
        left=right=nullptr;
    }
};
// ll cnt; vector<ll> a;
// bool query(ll l1, ll r1, ll l2, ll r2){
//     cnt++;
//     ll gcd1 = 0, gcd2=0;
//     for (ll i=l1; i<=r1; i++) gcd1=__gcd(gcd1, a[i]);
//     for (ll i=l2; i<=r2; i++) gcd2=__gcd(gcd2, a[i]);
//     return (gcd1==gcd2);
// }

void dfs(Node * cur, int *Left, int *Right){
    Left[cur->ind] = (cur->left?cur->left->ind:-1);
    Right[cur->ind] = (cur->right?cur->right->ind:-1);
    if (cur->left) dfs(cur->left, Left, Right);
    if (cur->right) dfs(cur->right, Left, Right);
}

int solve(ll n, int *Left, int *Right){
    Node * cur = new Node(0);
    vector<Node*> chain; chain.push_back(cur);
    Node * temp; Node * buffer;
    for (ll i=1; i<n; i++){
        if (query(chain.back()->ind, i, chain.back()->ind, chain.back()->ind)){
            temp = new Node(i);
            chain.back()->right=temp;
            chain.push_back(temp);
        }else{
            temp = new Node(i);
            while (!chain.empty() and query(i, i, chain.back()->ind, i)){
                buffer = chain.back();
                chain.pop_back();
            }
            temp->left = buffer;
            if (!chain.empty()) chain.back()->right=temp;
            chain.push_back(temp);
        }
    }
    dfs(chain[0], Left, Right);
    return chain[0]->ind;
}

// void solve(){
//     cnt=0; ll n; cin >> n; a.resize(n);
//     for (ll i=0; i<n; i++) cin >> a[i];
//     int Left[n], Right[n];
//     solve(n, Left, Right);
//     for (ll i=0; i<n; i++){
//         cout << Left[i] << " ";
//     }
//     cout << ln;
//     for (ll i=0; i<n; i++){
//         cout << Right[i] << " ";
//     }
//     cout << ln;
// }
// int main(){
//     ios_base::sync_with_stdio(false); cin.tie(nullptr);
//     auto start = chrono::high_resolution_clock::now();
//     ll t=1;
//     // cin >> t;
//     while (t--) solve();
//     #ifdef LOCAL
//     auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
//     cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
//     #endif
// }

• Subtask 1: 37 / 37
• Subtask 2: 24 / 24
• Subtask 3: 0 / 39