Submission #1312352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312352		Zbyszek99	Examination 2 (JOI24_examination2)	C++20	100 / 100	951 ms	746620 KiB

examination2

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = (1<<18);
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

struct node
{
    int l = 0;
    int r = INF-1;
    node* left = NULL;
    node* right = NULL;
    int nxt_one = INF;
    int nxt_zero = 0;
    int push = 0;
    int merges = 0;
    void sons()
    {
        if(left == NULL)
        {
            left = new node;
            left -> l = l;
            left -> r = (l+r)/2;
            left -> nxt_zero = l;
            right = new node;
            right -> l = (l+r)/2+1;
            right -> r = r;
            right -> nxt_zero = (l+r)/2+1;
        }
        if(push)
        {
            swap(left->nxt_one,left->nxt_zero);
            swap(right->nxt_one,right->nxt_zero);
            left->push ^= 1;
            right->push ^= 1;
            push = 0;
        }
    }
    void pull()
    {
        sons();
        nxt_one = min(left->nxt_one,right->nxt_one);
        nxt_zero = min(left->nxt_zero,right->nxt_zero);
    }
    void xor_seg(int l2, int r2)
    {
        if(r < l2 || l > r2) return;
        if(l >= l2 && r <= r2)
        {
            push ^= 1;
            swap(nxt_one,nxt_zero);
            return;
        }
        sons();
        left->xor_seg(l2,r2);
        right->xor_seg(l2,r2);
        pull();
    }
    int get_nxt_zero(int l2)
    {
        if(r < l2) return INF;
        if(l2 <= l) return nxt_zero;
        sons();
        return min(left->get_nxt_zero(l2),right->get_nxt_zero(l2));
    }
    int get_nxt_one(int l2)
    {
        if(r < l2) return INF;
        if(l2 <= l) return nxt_one;
        sons();
        return min(left->get_nxt_one(l2),right->get_nxt_one(l2));
    }
};

vi query_vals;

void set_dp(node& x, int a)
{
    int l = 0;
    int r = siz(query_vals)-1;
    int ans = siz(query_vals);
    while(l <= r)
    {
        int mid = (l+r)/2;
        if(query_vals[mid] >= a)
        {
            ans = mid;
            r = mid-1;
        }
        else
        {
            l = mid+1;
        }
    }
    x.xor_seg(ans,INF);
    x.merges = 1;
}

void not_dp(node& x)
{
    x.xor_seg(0,INF-1);
}

void and_dp(node& x, node& y)
{
    if(x.merges < y.merges) swap(x,y);
    x.merges += y.merges;
    int p = 0;
    while(true)
    {
        p = y.get_nxt_zero(p);
        if(p == INF) break;
        int r = y.get_nxt_one(p)-1;
        while(true)
        {
            int l2 = x.get_nxt_one(p);
            if(l2 > r) break;
            int r2 = min(r,x.get_nxt_zero(l2)-1);
            x.xor_seg(l2,r2);
        }
        p = r+1;
    }
}

void xor_dp(node& x, node& y)
{
    if(x.merges < y.merges) swap(x,y);
    x.merges += y.merges;
    int p = 0;
    while(true)
    {
        p = y.get_nxt_one(p);
        if(p == INF) break;
        int r = y.get_nxt_zero(p)-1;
        x.xor_seg(p,r);
        p = r+1;
    }
}

void or_dp(node& x, node& y)
{
    if(x.merges < y.merges) swap(x,y);
    x.merges += y.merges;
    int p = 0;
    while(true)
    {
        p = y.get_nxt_one(p);
        if(p == INF) break;
        int r = y.get_nxt_zero(p)-1;
        while(true)
        {
            int l2 = x.get_nxt_zero(p);
            if(l2 > r) break;
            int r2 = min(r,x.get_nxt_one(l2)-1);
            x.xor_seg(l2,r2);
        }
        p = r+1;
    }
}

int n;
string s;
int depth[1000001];
int ending[1000001];
int prev_oper[1000001][3];
int prev2[1000003][3];

void rek_depth(int l, int r, int d = 0)
{   
    rep2(i,l,r)
    {
        depth[i] = d;
        if(s[i] == '(')
        {
            depth[ending[i]] = d;
            rek_depth(i+1,ending[i]-1,d+1);
            i = ending[i];
            continue;
        }
    }
}

node rek(int l, int r)
{
    rep(o,3)
    {
        if(prev_oper[r][o] >= l)
        {
            node a1 = rek(l,prev_oper[r][o]-1);
            node a2 = rek(prev_oper[r][o]+1,r);
            if(o == 0) or_dp(a1,a2);
            if(o == 1) xor_dp(a1,a2);
            if(o == 2) and_dp(a1,a2);
            return a1;
        }
    }
    if(s[l] == '!')
    {
        node a = rek(l+1,r);
        not_dp(a);
        return a;
    }
    if(s[l] == '(') return rek(l+1,r-1);
    node a;
    int x = 0;
    rep2(i,l+1,r-1) x += pow(10,r-i-1)*(s[i]-'0');
    set_dp(a,x);
    return a;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    int n,q;
    cin >> n >> q >> s;
    vi queries;
    rep(qq,q)
    {
        int x;
        cin >> x;
        queries.pb(x);
        query_vals.pb(x);
    }
    sort(all(query_vals));
    int cur = 0;
    unordered_map<int,int> prev;
    for(int i = n-1; i >= 0; i--)
    {
        if(s[i] == ')')
        {
            cur++;
            prev[cur] = i;
        }
        if(s[i] == '(')
        {
            ending[i] = prev[cur];
            cur--;
        }
    }
    rek_depth(0,n-1);
    rep(d,3) rep(i,n) prev2[i][d] = -1;
    rep(i,n)
    {
        if(s[i] == '|') prev2[depth[i]][0] = i;
        if(s[i] == '^') prev2[depth[i]][1] = i;
        if(s[i] == '&') prev2[depth[i]][2] = i;
        rep(d,3) prev_oper[i][d] = prev2[depth[i]][d];
    }
    node ans_dp = rek(0,n-1);
    forall(it,queries)
    {
        int l = 0;
        int r = q-1;
        int ans = 0;
        while(l <= r)
        {
            int mid = (l+r)/2;
            if(query_vals[mid] >= it)
            {
                ans = mid;
                r = mid-1;
            }
            else
            {
                l = mid+1;
            }
        }
        if(ans_dp.get_nxt_one(ans) == ans) cout << "True\n";
        else cout << "False\n";
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 6 / 6
• Subtask 5: 12 / 12
• Subtask 6: 20 / 20
• Subtask 7: 27 / 27