Submission #208629

#	Time	Username	Problem	Language	Result	Execution time	Memory
208629		Samboor	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	25 ms	13264 KiB

semiexpress

#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <vector>
#include <utility>
#include <set>
#include <map>
#include <numeric>
#include <bitset>
#include <stack>
#include <queue>
#include <list>
#include <ctime>

using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair

ll n, m, k;
ll a, b, c; //local, exp, semi
ll t;
vector<ll> stop;
set<ll> seg;
map<ll, ll> interval; //przedzialy

void getInput()
{
    cin >> n >> m >> k;
    cin >> a >> b >> c;
    cin >> t;
    
    k-=m;
    
    for(int i=0, temp; i<m; i++)
        cin >> temp, stop.pb(temp);
}

void insert(ll p, ll q)
{    
    while(1)
    {
        auto it=seg.lower_bound(p);
        if(it==seg.begin())
            break;
            
        it--;
        if(p-interval[*it] > 1)
            break;
            
        p=min(p, *it);
        seg.erase(it);
    }
    
    while(1)
    {
        auto it=seg.lower_bound(p);
        
        if(it==seg.end())
            break;
            
        if((*it)-q <= 1)
        {
            q=max(q, interval[*it]);
            seg.erase(it);
            continue;
        }
        break;
    }
    
    seg.insert(p);
    interval[p]=q;
}

int query(ll p, ll q)
{
    auto it=seg.lower_bound(p);
    if(it!=seg.begin())
    {
        it--;
        p=max(p, interval[*it]+1);
    }
    
    it=seg.lower_bound(p);
    if(it!=seg.end())
        q=min(q, *it - 1);
        
    return max(0LL, q-p+1);
}

void getSegment()
{
    vector<pii> temp;
    
    for(int i=0; i<m; i++)
    {
        ll dist = (t - (b*(stop[i]-1)))/a;
        
        if((b*(stop[i]-1)) <= t)
            insert(stop[i], min(n, stop[i]+dist));
    }
}

priority_queue<pair<ll, pll>> que; //<wynik, <-pos, -end>>

void getSeg(int pos, ll maxi)
{
    //pos - stacja
    
    ll rem = t - (stop[pos]-1)*b;
    ll curr = stop[pos] + (rem/a);
    
    for(int i=0; i<k; i++)
    {
        curr++;
        
        if(curr >= maxi)
            return;
        
        if((curr-stop[pos])*c > rem)
            return;
            
        ll dist = curr + (rem - (curr-stop[pos])*c)/a;
        que.push(mp(dist-curr+1, mp(-curr, -dist)));
        curr += dist-curr;
    }
}

void printSeg()
{
    cout << "SEGMENT: \n";
    for(auto it=seg.begin(); it!=seg.end(); it++)
        cout << "[" << *it << ", " << interval[*it] << "], ";
    
    cout << endl;
}

void printQue(priority_queue<pair<ll, pll>> q)
{
    cout << "QUE: \n";
    while(!q.empty())
    {
        cout << "res: " << q.top().first << ": [" << q.top().second.first << ", " << q.top().second.second <<  "]\n";
        q.pop();     
    }
    cout << endl;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    /*int q;
    cin >> q;
    while(q--)
    {
        ll type, p, q;
        cin >> type >> p >> q; 
        if(type)
            cout << query(p, q) << endl;
        else
            insert(p, q), printSeg();
    }*/
    
    getInput();
    getSegment();
    
    stop.pb(n);
    for(int i=0; i<stop.size()-1; i++)
    {
        getSeg(i, stop[i+1]);
        //printQue(que);
    }
    
    //printQue(que);
    
    while(k)
    {
        if(que.empty())
            break;
        ll p = -que.top().second.first, dist=que.top().first;
        ll q = -que.top().second.second;
        que.pop();
        
        ll qu=query(p, q);
        
        if(1)
        {
            auto it=seg.lower_bound(p);
            if(it!=seg.begin())
                it--;
            
            if(p <= interval[*it])
                continue;
        }
        
        if(seg.find(p)==seg.end() && qu==dist)
            insert(p, q), k--;// cout << p << ", xD" << endl;
        else
            que.push(mp(qu, mp(-p, -q)));
    }
    
    //printSeg();
    ll res=-1;
    for(auto it=seg.begin(); it!=seg.end(); it++)
        res += interval[*it]-*it+1;
    
    //printSeg();
    cout << res;
    
    return 0;
}
 
 //1-36

Compilation message (stderr)

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:175:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<stop.size()-1; i++)
                  ~^~~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52