oj.uz

Submission #208629

# Submission time Handle Problem Language Result Execution time Memory
208629 2020-03-11T23:43:05 Z Samboor Semiexpress (JOI17_semiexpress) C++17
100 / 100
 25 ms 13264 KB 
#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

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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 248 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 388 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 248 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 388 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 380 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 248 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 388 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 380 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 380 KB Output is correct
22 Correct 6 ms 956 KB Output is correct
23 Correct 25 ms 13264 KB Output is correct
24 Correct 6 ms 760 KB Output is correct
25 Correct 5 ms 376 KB Output is correct
26 Correct 6 ms 380 KB Output is correct
27 Correct 6 ms 760 KB Output is correct
28 Correct 6 ms 632 KB Output is correct
29 Correct 20 ms 12888 KB Output is correct
30 Correct 15 ms 6752 KB Output is correct