Submission #1049519

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049519		Dennis_Jason	Sails (IOI07_sails)	C++14	25 / 100	1062 ms	6048 KiB

sails

#include <bitset>
#include <cmath>
#include <functional>
#include <algorithm>
#include <numeric>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <cstring>
#include <climits>
#define int long long
#define pb push_back
#define MOD 1000000007
#define NMAX 250001
#define nl '\n'
#define INF 1000000007
#define pii1 pair<int, pair<int,int>>  (1,(1,2));
#define pii pair<int,int>
#define tpl tuple<int,int,int>
using namespace std;
ifstream fin("data.in");
ofstream fout("data.out");
/*
    --------------------DEMONSTRATION---------------------

        3-2
        5-3
        4-1
        2-1
        4-3
        3-2

        subtask 1:1<=n<=15;

        5*(5+1)/2=10;
        1+2+3+4+5=15

    ------------------------END--------------------------

 */
class segtree{
private:
    int n;
    vector<int>tree;
public:
    void init(int sz)
    {
        n=sz;
        tree.resize(4*sz+1);
    }
    void update(int node,int st,int dr,int pos,int val)
    {
        if(st==dr)
        {
            tree[node]+=val;
            return;
        }
        int mid=(st+dr)/2;
        if(pos<=mid)
            update(2*node,st,mid,pos,val);
        else
            update(2*node+1,mid+1,dr,pos,val);
        tree[node]=tree[2*node]+tree[2*node+1];
    }
    pii combine(pii a,pii b)
    {
        if(a.first<b.first)
            return a;
        if(a.first==b.first)
        {
            if (a.second < b.second)
                return a;
            else
                return b;
        }
        else
            return b;


    }
    pii query(int node,int st,int dr,int L,int R)
    {
        if(st>R || dr<L)
            return {INF,-1};
        if(st==dr)
        {
            return {tree[node],st};
        }
        int mid=(st+dr)/2;
        pii a=query(2*node,st,mid,L,R);
        pii b=query(2*node+1,mid+1,dr,L,R);
        return min(a,b);
    }

    void update(int pos,int val)
    {
        update(1,1,n,pos,val);
    }
    pii query(int L,int R)
    {
        return query(1,1,n,L,R);
    }
};
int n,h,k;
int max_h;
vector<pii>v;

void subtask1()
{
    map<int,int>mp;
    for(int i=1;i<=max_h;++i)
    {
        mp[i]=0;
    }
    for(int i=1;i<=n;++i)
    {
        int maxi=v[i].first;
        int cnt=v[i].second;
        vector<int>aux;
        for(auto [x,y]:mp)
        {

            if(x>maxi)
                continue;
            aux.pb(x);
        }
        auto cmp=[&](int a,int b)
        {
            if(mp[a]==mp[b])
                return a>b;
            return mp[a]<mp[b];
        };
        sort(aux.begin(),aux.end(),cmp);
        for(auto x:aux)
        {
            if(!cnt)
                break;
            cnt--;
            mp[x]++;
        }

    }
    int ans=0;
    for(int i=1;i<=max_h;++i)
    {
//        cout<<mp[i]-1<<" ";
        if(mp[i])
        {
            mp[i]--;
            ans+=(mp[i]*(mp[i]+1))/2;
        }
    }
    cout<<ans;
}
segtree st;
void subtask2()
{
    st.init(max_h);
    int cnt=v[n].second;
    for(int i=v[n].first;i>=1 && cnt;--i)
    {
        st.update(i,1);
        cnt--;
    }
//    for(int i=1;i<=max_h;++i)
//    {
//        cout<<st.query(i,i).first<<nl;
//    }

    for(int i=n-1;i>=1;--i)
    {
//        cout<<i<<": ";
        vector<pii>interval;
        interval.pb({1,v[i].first});
        for(int j=1;j<=v[i].second;++j)
        {
//            cout<<nl;
            pii mini={INF,INF};
            for(auto [x,y]:interval)
            {
//                cout<<x<<" "<<y<<" ";
                mini=min(mini,st.query(x,y));
            }
            st.update(mini.second,1);
//            cout<<mini.second<<" ";
           for(int i=0;i<interval.size();++i)
           {
               auto [x,y]=interval[i];
               if(mini.second>=x && mini.second<=y)
               {
                   if(mini.second-1>=1 && x<=mini.second-1)
                        interval[i]={x,mini.second-1};
                   else
                       interval[i]={0,0};
                   if(mini.second+1<=max_h && mini.second+1<=y)
                        interval.pb({mini.second+1,y});

                   break;
               }
           }
        }
//        cout<<nl;
    }
    int ans=0;
    for(int i=1;i<=max_h;++i)
    {
        int aux=st.query(i,i).first;
        aux--;
//        cout<<aux<<" ";
        ans+=((aux*(aux+1))/2);
    }
    cout<<ans;
}
signed main() {

    cin>>n;
    v.resize(n+1);
    for(int i=1;i<=n;++i)
    {
        cin>>h>>k;
        v[i]={h,k};
        max_h=max(max_h,h);
    }
    if(n<=15)
    {
        subtask1();
        return 0;
    }
    else
    {
        subtask2();
    }




    return 0;
}

Compilation message (stderr)

sails.cpp: In function 'void subtask1()':
sails.cpp:131:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  131 |         for(auto [x,y]:mp)
      |                  ^
sails.cpp: In function 'void subtask2()':
sails.cpp:190:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  190 |             for(auto [x,y]:interval)
      |                      ^
sails.cpp:197:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  197 |            for(int i=0;i<interval.size();++i)
      |                        ~^~~~~~~~~~~~~~~~
sails.cpp:199:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  199 |                auto [x,y]=interval[i];
      |                     ^

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10