oj.uz

Submission #799815

# Submission time Handle Problem Language Result Execution time Memory
799815 2023-08-01T05:13:31 Z n3rm1n Exhibition (JOI19_ho_t2) C++17
0 / 100
 1 ms 212 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const long long MAXN = 1e5 + 10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
long long n, m;
vector < pair < long long , long long > > g;
vector < long long > frames;
void read()
{
    cin >> n >> m;
    long long xx, yy;
    for (long long i = 1; i <= n; ++ i)
    {
        cin >> xx >> yy;
        g.push_back(make_pair(yy, xx));
    }
    sort(g.begin(), g.end());
    for (long long i = 1; i <= m; ++ i)
    {
        cin >> xx;
        frames.push_back(-xx);
    }
    sort(frames.begin(), frames.end());
}
vector < long long > v;
bool check(long long goal)
{
    v.clear();
     v.push_back(-1);
    long long x;
    long long sz = goal-1;
    for (long long i = 0; i < g.size(); ++ i)
    {
        x = g[i].second;
        if(/*x >= (long long)v.back() &&*/ x <= -frames[sz])
        {
            v.push_back(x);
            sz --;
            if(sz < 0)return true;
        }
        else
        {
            for (int j = 1; j < v.size(); ++ j)
            {
                if(v[j] > x)
                {

                    cout << "update" << endl;
                    cout << j << " " << v[j] << " " << x << endl;
                    v[j] = x;
                    break;
                }
            }

            /*vector < long long >::iterator it = upper_bound(v.begin(), v.end(), x);
           // if(it == v.end())continue;
            long long num = *it, index = it - v.begin();
            cout << "update" << endl;
            if(index >= v.size())continue;
            v[index] = x;*/
        }
    }
    if(goal == 2)
    {
        cout << "! " << v[1] << endl;
    }
   return (sz < 0);
}
void bin_search()
{
    long long l = 1, r = m, mid, ans = 0;
    while(l <= r)
    {
        mid = (l + r)/2;
        if(check(mid))
        {
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    cout << ans << endl;
}
int main()
{
    speed();

    read();
    bin_search();
    return 0;
}
/**
10 10
978749728 144544247
765886828 382970504
724321206 775440108
793469869 329793955
744661733 757784475
737531928 772848949
880702330 298220471
886356598 234769581
756489712 541017091
976784156 205683907
498207927
462526472
688444509
591128229
744661733
421432475
299894333
737531928
39584784
724321206

10 10
44994472 57160841
127592536 57160841
60187289 57160841
224262980 801083909
297577794 801083909
521325580 801083909
802591211 801083909
333555245 57160841
362230938 57160841
52476098 57160841
465120061
652114335
652114335
465120061
467708607
874271777
467708607
467708607
874271777
465120061

*/

Compilation message

joi2019_ho_t2.cpp: In function 'bool check(long long int)':
joi2019_ho_t2.cpp:38:29: 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]
   38 |     for (long long i = 0; i < g.size(); ++ i)
      |                           ~~^~~~~~~~~~
joi2019_ho_t2.cpp:49:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             for (int j = 1; j < v.size(); ++ j)
      |                             ~~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -