제출 #1168274

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1168274		KaleemRazaSyed	새로운 문제 (POI13_ins)	C++20	0 / 100	3250 ms	7060 KiB

ins

#include<bits/stdc++.h>

using namespace std;

int main()
{
  int _;
  cin >> _;
  while(_--)
    {
      int n, m;
      cin >> n >> m;

      int t[m], p[m], c[m];
      for(int i = 0; i < m; i ++) {
	cin >> t[i] >> p[i] >> c[i];
	t[i]--, c[i]++;
	p[i]--;
      }
  
      int l = 0, r = m+1;

      while(r - l > 1)
	{
	  int mid = (l + r) / 2;

	  int sz[m] = {}, mx[n];
	  vector<int> pro[m];
	  memset(sz, -1, sizeof(sz));
	  memset(mx, -1, sizeof(mx));

	  bool True = true;
      
	  for(int i = 0 ; i < mid;  i++)
	    {
	      pro[t[i]].push_back(p[i]);
	      mx[p[i]] = max(mx[p[i]], t[i]);
	      if(sz[t[i]] == -1)
		sz[t[i]] = c[i];
	      else if(sz[t[i]] != c[i])
		True = false;
	    }

	  set<pair<int,int> > pt;
	  for(int i = 0; i < m ;i ++)
	    {
	      for(int x : pro[i])
		pt.insert({mx[x], x});

	      if(pt.size() > sz[i] && sz[i] != -1)
		True = false;

	      while(pt.size() && pt.begin()->first <= i)
		pt.erase(pt.begin());
	    }    
	  //	  cerr << "True = " << True << ' ' << mid << endl;

	  if(True) l = mid;
	  else r = mid;
	}
  
  
      cout << l << endl;
    }
  return  0;
}

• Subtask 1: 0 / 100