Submission #928418

#	Time	Username	Problem	Language	Result	Execution time	Memory
928418		cpptowin	Matryoshka (JOI16_matryoshka)	C++17	100 / 100	127 ms	23888 KiB

matryoshka

#include<bits/stdc++.h>
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout<<"\n";
#define int long long
#define inf (int)1e18
#define pii pair<int,int>
#define vii vector<pii>
#define lb(x) x&-x
#define bit(i,j) ((i>>j)&1)
#define offbit(i,j) (i^(1<<j))
#define onbit(i,j) (i|(1<<j))
#define vi vector<int>
template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
int n,q;
pii a[maxn];
array<int,3> qry[maxn];
vi v;
int ans[maxn];
main()
{
    #define name "TASK"
    if(fopen(name".inp","r"))
    {
       freopen(name".inp","r",stdin);
       freopen(name".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin >> n >> q;
    fo(i,1,n)
    {
        cin >> a[i].fi >> a[i].se;
    }
    fo(i,1,q)
    {
        cin >> qry[i][0] >> qry[i][1];
        qry[i][2] = i;
    }
    sort(qry + 1,qry + q + 1,greater<array<int,3>>());
    sort(a + 1,a + n + 1,[](pii a,pii b)
         {
             return a.fi > b.fi or (a.fi == b.fi and a.se < b.se);
         });
    int j = 0;
    fo(i,1,q)
    {
        while(qry[i][0] <= a[j + 1].fi and j < n)
        {
            j++;
            int lb = upper_bound(v.begin(),v.end(),a[j].se) - v.begin();
            if(lb < v.size()) v[lb] = a[j].se;
            else v.pb(a[j].se);
        }
        ans[qry[i][2]] = upper_bound(v.begin(),v.end(),qry[i][1]) - v.begin();
    }
    fo(i,1,q) cout << ans[i] << "\n";
}

Compilation message (stderr)

matryoshka.cpp:29:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   29 | main()
      | ^~~~
matryoshka.cpp: In function 'int main()':
matryoshka.cpp:60:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |             if(lb < v.size()) v[lb] = a[j].se;
      |                ~~~^~~~~~~~~~
matryoshka.cpp:34:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |        freopen(name".inp","r",stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
matryoshka.cpp:35:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |        freopen(name".out","w",stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 49 / 49