Submission #22168

#	Time	Username	Problem	Language	Result	Execution time	Memory
22168		_(:3」∠)_ (#42)	구간들 (KRIII5P_3)	C++11	7 / 7	329 ms	13416 KiB

i

#include <cstdio>
#include <utility>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

const int MOD = 1000000007;

vector<pair<int, int> > p;
vector<int> xs; map<int, int> xi;
int tr[200010];

int pow2(int x){
  int res = 1, pw = 2;
  while(x > 0){
    if(x % 2 == 1) res = 1LL * res * pw % MOD;
    pw = 1LL * pw * pw % MOD; x /= 2;
  }
  return res;
}

int main(){
  int N; scanf("%d", &N);

  xs.push_back(-1);
  for(; N--; ){
    int s, e; scanf("%d%d", &s, &e);
    if(s >= e) continue;
    xs.push_back(s); xs.push_back(e);
    p.push_back({e, s});
  }
  N = p.size();

  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());

  int xc = (int)xs.size() - 1;
  for(int i = 1; i <= xc; i++) xi[xs[i]] = i;

  for(int i = 0; i < N; i++){
    p[i].first = xi[p[i].first];
    p[i].second = xi[p[i].second];
  }

  sort(p.begin(), p.end());

  // distance sum
  int ds = 0;

  for(int i = xc, pi = N - 1; i > 1; i--){
    while(pi >= 0 && p[pi].first == i){
      for(int x = p[pi].second; x <= xc; x += x & -x) tr[x]++;
      pi--;
    }

    int s = 0;
    for(int x = i - 1; x > 0; x -= x & -x) s += tr[x];

    ds += 1LL * (pow2(s) - 1) * (xs[i] - xs[i - 1]) % MOD;
    if(ds >= MOD) ds -= MOD;
  }

  // number of sets
  int cnt = 0;
  for(int i = 1; i <= xc; i++) tr[i] = 0;

  for(int i = N - 1; i >= 0; i--){
    int s = 0;
    for(int x = p[i].first - 1; x > 0; x -= x & -x) s += tr[x];

    cnt += pow2(s); if(cnt >= MOD) cnt -= MOD;
    for(int x = p[i].second; x <= xc; x += x & -x) tr[x]++;
  }

  printf("%d %d\n", ds, cnt);
  return 0;
}

Compilation message (stderr)

i.cpp: In function 'int main()':
i.cpp:24:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int N; scanf("%d", &N);
                         ^
i.cpp:28:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int s, e; scanf("%d%d", &s, &e);
                                    ^

• Subtask 1: 7 / 7