Submission #1035952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035952		amine_aroua	Arranging Tickets (JOI17_arranging_tickets)	C++17	0 / 100	1 ms	348 KiB

arranging_tickets

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct Node
{
    int sum , cnt;
    Node(){
        sum = cnt = 0;
    }
};
struct segTree
{
    vector<Node> tree;
    int BASE;
    void build(int n)
    {
        BASE = n;
        while(__builtin_popcount(BASE) != 1)
        {
            BASE++;
        }
        tree.assign(4*BASE , Node());
    }
 
    void upd(int node , int s , int e ,int l , int r , int val)
    {
        if(l > e || s > r)
            return ;
        if(l <= s && e <= r)
        {
            tree[node].cnt+=val;
        }
        else
        {
            int m = (s + e)>>1;
            upd(node<<1 , s , m , l , r , val);
            upd(node<<1|1 , m + 1 , e , l , r , val);
        }
        if(tree[node].cnt)
        {
            tree[node].sum = e - s + 1;
        }
        else
            tree[node].sum = tree[node<<1].sum + tree[node<<1|1].sum;
    }   
    void upd(int l , int r , int val)
    {
        if(l > r)
            return;
        upd(1 , 0 , BASE - 1 , l , r , val);
    }
};
 
 
void run_case()
{
    int n , m;
    cin>>n>>m;
    segTree seg;
    seg.build(n);
    vector<int> in[n + 1] , out[n + 1];
    for(int i = 0 ; i < m ; i++)
    {
        int a , b , c;
        cin>>a>>b>>c;
        a-- , b--;
        in[a].push_back(b);
        out[b].push_back(a);
        seg.upd(a , b - 1 , 1);
    }
    
    int ans = n;
    for(int i = 0 ; i <= n ; i++)
    {
        ans = min(ans , seg.tree[1].sum);
        for(auto j : in[i])
        {
            seg.upd(i , j - 1, -1);
            seg.upd(0 , i - 1 , 1);
            seg.upd(j , n - 1 , 1);
        }
        for(auto j : out[i])
        {
            seg.upd(j , i - 1, 1);
            seg.upd(0 , j - 1 , -1);
            seg.upd(i , n - 1 , -1);
        }
    }
    cout<<ans<<'\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    //cin>>t;
    while (t--)
    {
        run_case();
    }
    
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 35
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 15