답안 #22167

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
22167	2017-04-29T13:43:32 Z	_(:3」∠)_(#1025, xdoju)	구간들 (KRIII5P_3)	C++11	0 / 7	133 ms	7640 KB

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[100010], k[100010];

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

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

0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1960 KB	Output is correct
2	Correct	0 ms	1960 KB	Output is correct
3	Correct	0 ms	1960 KB	Output is correct
4	Correct	0 ms	1960 KB	Output is correct
5	Correct	0 ms	1960 KB	Output is correct
6	Correct	6 ms	2252 KB	Output is correct
7	Correct	6 ms	2252 KB	Output is correct
8	Correct	6 ms	2252 KB	Output is correct
9	Correct	6 ms	2252 KB	Output is correct
10	Correct	6 ms	2252 KB	Output is correct
11	Correct	73 ms	4692 KB	Output is correct
12	Correct	66 ms	4692 KB	Output is correct
13	Correct	86 ms	4692 KB	Output is correct
14	Correct	69 ms	4692 KB	Output is correct
15	Correct	76 ms	4692 KB	Output is correct
16	Runtime error	133 ms	7640 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Halted	0 ms	0 KB	-