提出 #1320354


ソースコード 拡げる

Copy
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
int N=1<<19;
class StarrySkyTree{
public:
  ll Mi[555555*2],A[555555*2];
  void init(){fill(Mi,Mi+555555*2,0);fill(A,A+555555*2,0);}
  void add(int a,int b,int x,int k=0,int l=0,int r=N) {
    if(r<=a||b<=l) return;
    if(a<=l&&r<=b){
      A[k]+=x;
      while(k){
        k=(k-1)/2;
        Mi[k]=min(Mi[k*2+1]+A[k*2+1],Mi[k*2+2]+A[k*2+2]);
      }
      return;
    }
    add(a,b,x,k*2+1,l,(l+r)/2);
    add(a,b,x,k*2+2,(l+r)/2,r);
  }
  ll getMin(int a,int b,int k=0,int l=0,int r=N) {
    if(r<=a||b<=l)return LLONG_MAX;if(a<=l&&r<=b)return Mi[k]+A[k];
    ll left=getMin(a,b,k*2+1,l,(l+r)/2),right=getMin(a,b,k*2+2,(l+r)/2,r);
    return min(left,right)+A[k];
  }
};

StarrySkyTree t;
int main() {
  t.init();
  int n,m;
  cin >> n >> m;
  P a[m];
  for(int i=0; i<m; i++) {
    cin >> a[i].first >> a[i].second;
    t.add(a[i].first,a[i].second+1,1);
  }
  vector<int> ans;
  for(int i=0; i<m; i++) {
    if(t.getMin(a[i].first,a[i].second+1)>1) ans.push_back(i+1);
  }
  cout << ans.size() << endl;
  for(int i=0; i<ans.size(); i++) cout << ans[i] << endl;
  return 0;
}

提出情報

提出日時
問題 B - ドキドキデート大作戦高橋君
ユーザ kzyKT
言語 C++14 (GCC 5.4.1)
得点 100
コード長 1218 Byte
結果
実行時間 351 ms
メモリ 20216 KB

テストケース

セット名 得点 / 配点 テストケース
Sample 0 / 0 subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt
Subtask1 30 / 30 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt
All 70 / 70 subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt
ケース名 結果 実行時間 メモリ
subtask0_sample_01.txt 6 ms 17664 KB
subtask0_sample_02.txt 6 ms 17664 KB
subtask0_sample_03.txt 6 ms 17664 KB
subtask1_01.txt 103 ms 19200 KB
subtask1_02.txt 262 ms 20216 KB
subtask1_03.txt 100 ms 19200 KB
subtask1_04.txt 187 ms 19836 KB
subtask1_05.txt 189 ms 19836 KB
subtask1_06.txt 6 ms 17664 KB
subtask1_07.txt 6 ms 17664 KB
subtask1_08.txt 6 ms 17664 KB
subtask1_09.txt 6 ms 17664 KB
subtask2_01.txt 336 ms 20216 KB
subtask2_02.txt 319 ms 20216 KB
subtask2_03.txt 6 ms 17664 KB
subtask2_04.txt 6 ms 17664 KB
subtask2_05.txt 6 ms 17664 KB
subtask2_06.txt 6 ms 17664 KB
subtask2_07.txt 6 ms 17664 KB
subtask2_08.txt 351 ms 20216 KB