Submission #987367

#	Time	Username	Problem	Language	Result	Execution time	Memory
987367		amine_aroua	Arranging Tickets (JOI17_arranging_tickets)	C++17	10 / 100	55 ms	500 KiB

arranging_tickets

#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define int long long
#define pb push_back
#define nl '\n'
#define fore(i, y) for(int i = 0; i < y; i++)
#define forr(i, x, y) for(int i = x;i<=y;i++)
#define forn(i, y, x) for(int i = y; i >= x; i--)
const int INF = 1e9;
int comb(int a , int b)
{
    return max(a , b);
}
struct segTree
{
    int BASE;
    vector<int> tree;
    vector<int> lazy;
    void build(int n)
    {
        BASE = n;
        while(__builtin_popcount(BASE) != 1)
            BASE++;
        tree.clear();
        lazy.clear();
        tree.assign(2*BASE , 0);
        lazy.assign(2*BASE , 0);
    }
    void propag(int node , int x)
    {
        if(lazy[node] == 0)
            return ;
        forr(lt , 2*node , 2*node + 1)
        {
            lazy[lt]+=lazy[node];
            tree[lt]+=lazy[node];
        }
        lazy[node] = 0;
    }
    void upd(int node , int s , int e , int l , int r , int v)
    {
        if(l <= s && e <= r)
        {
            lazy[node]+=v;
            tree[node]+=v;
            return ;
        }
        if(l > e || s > r)
            return;
        propag(node , (e - s + 1)/2);
        int mid = (s + e)>>1;
        upd(2*node , s , mid , l , r , v);
        upd(2*node + 1 , mid + 1 , e , l , r , v);
        tree[node] = comb(tree[2*node] , tree[2*node + 1]);
    }
    int query(int node , int s , int e , int l , int r)
    {
        if(l <= s && e <= r)
        {
            return tree[node];
        }
        if(l > e || s > r)
            return 0;
        propag(node , (e - s + 1)/2);
        int mid = (s + e)>>1;
        return comb(query(2*node , s , mid , l , r ) , query(2*node + 1 , mid + 1 , e , l , r ));
    }
    int query(int l ,int r)
    {
        if(l > r)
            return 0;
        return query(1 , 0 , BASE - 1 , l , r);
    }
    void upd(int l , int r , int v)
    {
        if(l > r)
            return ;
        upd(1 , 0 , BASE - 1 , l , r , v);
    }
}tree[2];

struct Qu
{
    int A , B , C;
};
int n , m;
vector<pair<int ,int>> getVals(int C , int maxIn , int maxOut)
{
    return {{0 , 1} , {1 , 0}};
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ans = INF;
    cin>>n>>m;
    vector<Qu> queries(m);
    fore(i , m)
    {
        cin>>queries[i].A>>queries[i].B>>queries[i].C;
        if(queries[i].A > queries[i].B)
            swap(queries[i].A , queries[i].B);
    }
    int cnt = 40;
    while(cnt--)
    {
        random_shuffle(queries.begin() , queries.end());
        fore(i , 2)
            tree[i].build(n + 1);
        vector<pair<int ,int>> cur = getVals(queries[0].C , 0  ,0);
        fore(i , 2)
        {
            tree[i].upd(queries[0].A , queries[0].B - 1, cur[i].first);
            tree[i].upd(1 , queries[0].A - 1 , cur[i].second);
            tree[i].upd(queries[0].B , n , cur[i].second);
        }
        forr(k , 1 , m - 1)
        {
            fore(i , 2)
            {
                int best[2] = {INF , INF};
                int maxIn = tree[i].query(queries[k].A , queries[k].B - 1);
                int maxOut = max(tree[i].query(1 , queries[k].A - 1) , tree[i].query(queries[k].B , n));
                cur = getVals(queries[k].C , maxIn , maxOut);
                fore(j , 2)
                {
                    tree[i].upd(queries[k].A , queries[k].B - 1, cur[j].first);
                    tree[i].upd(1 , queries[k].A - 1 , cur[j].second);
                    tree[i].upd(queries[k].B , n , cur[j].second);
                    best[j] = tree[i].tree[1];
                    tree[i].upd(queries[k].A , queries[k].B - 1, -cur[j].first);
                    tree[i].upd(1 , queries[k].A - 1 , -cur[j].second);
                    tree[i].upd(queries[k].B , n , -cur[j].second);
                }
                if(best[0] < best[1])
                {
                    int j = 0;
                    tree[i].upd(queries[k].A , queries[k].B - 1, cur[j].first);
                    tree[i].upd(1 , queries[k].A - 1 , cur[j].second);
                    tree[i].upd(queries[k].B , n , cur[j].second);
                }
                else
                {
                    int j = 1;
                    tree[i].upd(queries[k].A , queries[k].B - 1, cur[j].first);
                    tree[i].upd(1 , queries[k].A - 1 , cur[j].second);
                    tree[i].upd(queries[k].B , n , cur[j].second);
                }
            }
        }
        ans = min({ans , tree[0].tree[1] , tree[1].tree[1]});
    }
    cout<<ans<<nl;
}

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