Submission #109694

#	Time	Username	Problem	Language	Result	Execution time	Memory
109694		ffresh	Matryoshka (JOI16_matryoshka)	C++17	11 / 100	3 ms	384 KiB

matryoshka

#include <bits/stdc++.h>
using namespace std;

const int N = 105;

int R[N],H[N];
void solve() {
   int n,q;
   scanf("%d%d",&n,&q);
   for(int i=0;i<n;++i) {
      scanf("%d%d",&R[i],&H[i]);
   }

   for(int i=0;i<q;++i) {
      vector<pair<int,int> > in;
      int a,b;
      scanf("%d%d",&a,&b);
      for(int j = 0;j<n;++j) {
         if(R[j]>=a && H[j]<=b) {
            in.push_back(make_pair(R[j],H[j]));
         }
      }
      sort(in.begin(),in.end());
      multiset<pair<int,int> >s;
      
      int ret = 0;
      for(int j = 0;j<in.size();++j) {
         s.insert(make_pair(in[j].second,in[j].first));
      }
      for(int j = in.size()-1;j>=0;) {
         int k;
         for(k = j;k>=0;--k) {
            if(in[j].first!= in[k].first) {
               break;
            }
            //cout<<in[k].first<<endl;
            if(s.count(make_pair(in[k].second,in[k].first))){
               ++ret;
               multiset<pair<int,int> > ::iterator it = s.find(make_pair(in[k].second,in[k].first));
               s.erase(it);
            }
         }
         for(k = j;k>=0;--k) {
            if(in[j].first != in[k].first) {
               break;
            }
            int g = in[k].second;
            multiset<pair<int,int> >::iterator it = s.lower_bound(make_pair(g,0));
            if(it != s.begin()) {
               it = prev(it);
               s.erase(it);
            }
         }
         j = k;
      }
      printf("%d\n", ret);
   }
}
int main()
{
    //freopen("input.txt","r",stdin);
    solve();
}

Compilation message (stderr)

matryoshka.cpp: In function 'void solve()':
matryoshka.cpp:27:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int j = 0;j<in.size();++j) {
                     ~^~~~~~~~~~
matryoshka.cpp:9:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d",&n,&q);
    ~~~~~^~~~~~~~~~~~~~
matryoshka.cpp:11:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d%d",&R[i],&H[i]);
       ~~~~~^~~~~~~~~~~~~~~~~~~~
matryoshka.cpp:17:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d%d",&a,&b);
       ~~~~~^~~~~~~~~~~~~~

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