Submission #987331

#	Time	Username	Problem	Language	Result	Execution time	Memory
987331		amine_aroua	Arranging Tickets (JOI17_arranging_tickets)	C++17	0 / 100	1 ms	344 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--)
int BASE;
vector<int> tree[2];
vector<int> lazy;
int comb(int a , int b , int k)
{
    if(k == 0)
        return a + b;
    return max(a , b);
}
void build(int n)
{
    BASE = n;
    while(__builtin_popcount(BASE) != 1)
        BASE++;
    fore(i , 2)
        tree[i].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[0][lt]+=lazy[node] * x;
        tree[1][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[0][node]+=v * (e - s + 1);
        tree[1][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);
    fore(i , 2)
        tree[i][node] = comb(tree[i][2*node] , tree[i][2*node + 1] , i);
}
int query(int node , int s , int e , int l , int r , int v)
{
    if(l <= s && e <= r)
    {
        return tree[v][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 , v) , query(2*node + 1 , mid + 1 , e , l , r , v) , v);
}
int query(int l ,int r ,int v)
{
    if(l > r)
        return 0;
    return query(1 , 0 , BASE - 1 , l , r , v);
}
void upd(int l , int r , int v)
{
    if(l > r)
        return ;
    upd(1 , 0 , BASE - 1 , l , r , v);
}
int n , m;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    vector<vector<int>> queries;
    build(n + 1);
    fore(i , m)
    {
        int a , b , c;
        cin>>a>>b>>c;
        queries.pb({c , a , b});
    }
    sort(queries.begin() , queries.end());
    for(auto Q : queries)
    {
        int A = Q[1] , B = Q[2] , C = Q[0];
        if(A > B)
            swap(A , B);
        int maxIn = query(A , B - 1 , 1) , maxOut = comb(query(1 , A - 1 , 1) , query(B , n , 1) , 1);
        int cte = maxOut - maxIn;
        int a = max(0ll , (int)(C - cte)/2);
        int b = C - a;
        if(a + maxIn == b + maxOut)
        {
            upd(1 , A - 1 , b);
            upd(B , n , b);
            upd(A , B - 1 , a);
        }
        else
        {
            if(query(A , B - 1 , 0) < query(1 , A - 1 , 0) + query(B , n , 0))
            {
                if(a < b)
                    swap(a , b);
            }
            else if(query(A , B - 1 , 0) > query(1 , A - 1 , 0) + query(B , n , 0))
            {
                if(a > b)
                    swap(a , b);
            }
            else
            {
                if(b - a > n - (b - a))
                {
                    if(a > b)
                        swap(a , b);
                }
                else
                {
                    if(a < b)
                        swap(a , b);
                }
            }
            upd(1 , A - 1 , b);
            upd(B , n , b);
            upd(A , B - 1 , a);
        }
    }
    cout<<tree[1][1]<<nl;
}

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