답안 #59335 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59335	2018-07-21T14:50:09 Z	gusfring	운세 보기 2 (JOI14_fortune_telling2)	C++14	100 / 100	2392 ms	148700 KB

fortune_telling2

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

const int maxn = 2e5 + 5;

int n,m;
int a[maxn], b[maxn], c[maxn];
int pos[maxn], res[maxn];
vector<int> p[maxn];

int sz;
int limit, tree[maxn*9];
int fen[maxn*3];

map<int,int> mp;
int rec[maxn*3];

void cpidx() {
  for(int i=1; i<=n; i++) mp[a[i]], mp[b[i]];
  for(int i=1; i<=m; i++) mp[c[i]];
  for(auto &it : mp){
    it.second = ++sz;
    rec[sz] = it.first;
  }
  for(int i=1; i<=n; i++) a[i] = mp[a[i]], b[i] = mp[b[i]];
  for(int i=1; i<=m; i++) c[i] = mp[c[i]];
}

void init(){
  limit = 1;
  while(limit<=sz) limit*=2;
}

void update(int x, int val){
  x += limit;
  tree[x] = max(tree[x], val);
  while(x){
    x/=2;
    tree[x] = max(tree[x<<1], tree[x<<1|1]);
  }
}

int query(int l, int r){
  l += limit; r += limit;
  int res = 0;
  while(l<r){
    if(l % 2 != 0) res = max(res, tree[l++]);
    if(r % 2 == 0) res = max(res, tree[r--]);
    l/=2; r/=2;
  }
  if(l == r) res = max(res, tree[l]);
  return res;
}

void add(int x, int val){
  while(x){
    fen[x] += val;
    x -= x&-x;
  }
}
int sum(int x){
  int res = 0;
  while(x<=sz){
    res += fen[x];
    x += x&-x;
  }
  return res;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++) scanf("%d%d",&a[i],&b[i]);
    for(int i=1; i<=m; i++) scanf("%d",&c[i]);
    cpidx();
    init();
    for(int i=1; i<=m; i++) update(c[i], i);
    for(int i=1; i<=n; i++) {
      pos[i] = query(min(a[i],b[i]), max(a[i],b[i])-1);
      p[pos[i]+1].push_back(i);
    }
    for(int i=m; i>=1; i--){
      add(c[i],1);
      for(auto x : p[i]) res[x] = sum(max(a[x], b[x]));
    }
    long long ans = 0;
    for(int i=1; i<=n; i++){
      if(pos[i]==0){
        if(res[i] % 2 == 0) ans += rec[a[i]];
        else ans += rec[b[i]];
      }
      else{
        if(res[i] % 2 == 1) ans += rec[min(a[i], b[i])];
        else ans += rec[max(a[i], b[i])];
      }
    }
    printf("%lld",ans);
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
fortune_telling2.cpp:72:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1; i<=n; i++) scanf("%d%d",&a[i],&b[i]);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:73:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1; i<=m; i++) scanf("%d",&c[i]);
                             ~~~~~^~~~~~~~~~~~

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	5112 KB	Output is correct
2	Correct	9 ms	5368 KB	Output is correct
3	Correct	11 ms	5368 KB	Output is correct
4	Correct	11 ms	5456 KB	Output is correct
5	Correct	12 ms	5564 KB	Output is correct
6	Correct	10 ms	5564 KB	Output is correct
7	Correct	10 ms	5564 KB	Output is correct
8	Correct	11 ms	5708 KB	Output is correct
9	Correct	11 ms	5708 KB	Output is correct
10	Correct	10 ms	5708 KB	Output is correct
11	Correct	10 ms	5708 KB	Output is correct
12	Correct	11 ms	5752 KB	Output is correct
13	Correct	12 ms	5912 KB	Output is correct

Subtask #2
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	5112 KB	Output is correct
2	Correct	9 ms	5368 KB	Output is correct
3	Correct	11 ms	5368 KB	Output is correct
4	Correct	11 ms	5456 KB	Output is correct
5	Correct	12 ms	5564 KB	Output is correct
6	Correct	10 ms	5564 KB	Output is correct
7	Correct	10 ms	5564 KB	Output is correct
8	Correct	11 ms	5708 KB	Output is correct
9	Correct	11 ms	5708 KB	Output is correct
10	Correct	10 ms	5708 KB	Output is correct
11	Correct	10 ms	5708 KB	Output is correct
12	Correct	11 ms	5752 KB	Output is correct
13	Correct	12 ms	5912 KB	Output is correct
14	Correct	58 ms	8144 KB	Output is correct
15	Correct	111 ms	10868 KB	Output is correct
16	Correct	202 ms	13772 KB	Output is correct
17	Correct	298 ms	17292 KB	Output is correct
18	Correct	290 ms	18344 KB	Output is correct
19	Correct	317 ms	19496 KB	Output is correct
20	Correct	287 ms	20672 KB	Output is correct
21	Correct	306 ms	21768 KB	Output is correct
22	Correct	155 ms	21768 KB	Output is correct
23	Correct	109 ms	21768 KB	Output is correct
24	Correct	94 ms	21768 KB	Output is correct
25	Correct	137 ms	22592 KB	Output is correct
26	Correct	152 ms	22592 KB	Output is correct
27	Correct	186 ms	24252 KB	Output is correct
28	Correct	172 ms	25576 KB	Output is correct
29	Correct	240 ms	27936 KB	Output is correct

Subtask #3
65.0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	5112 KB	Output is correct
2	Correct	9 ms	5368 KB	Output is correct
3	Correct	11 ms	5368 KB	Output is correct
4	Correct	11 ms	5456 KB	Output is correct
5	Correct	12 ms	5564 KB	Output is correct
6	Correct	10 ms	5564 KB	Output is correct
7	Correct	10 ms	5564 KB	Output is correct
8	Correct	11 ms	5708 KB	Output is correct
9	Correct	11 ms	5708 KB	Output is correct
10	Correct	10 ms	5708 KB	Output is correct
11	Correct	10 ms	5708 KB	Output is correct
12	Correct	11 ms	5752 KB	Output is correct
13	Correct	12 ms	5912 KB	Output is correct
14	Correct	58 ms	8144 KB	Output is correct
15	Correct	111 ms	10868 KB	Output is correct
16	Correct	202 ms	13772 KB	Output is correct
17	Correct	298 ms	17292 KB	Output is correct
18	Correct	290 ms	18344 KB	Output is correct
19	Correct	317 ms	19496 KB	Output is correct
20	Correct	287 ms	20672 KB	Output is correct
21	Correct	306 ms	21768 KB	Output is correct
22	Correct	155 ms	21768 KB	Output is correct
23	Correct	109 ms	21768 KB	Output is correct
24	Correct	94 ms	21768 KB	Output is correct
25	Correct	137 ms	22592 KB	Output is correct
26	Correct	152 ms	22592 KB	Output is correct
27	Correct	186 ms	24252 KB	Output is correct
28	Correct	172 ms	25576 KB	Output is correct
29	Correct	240 ms	27936 KB	Output is correct
30	Correct	520 ms	37708 KB	Output is correct
31	Correct	924 ms	46540 KB	Output is correct
32	Correct	1362 ms	57496 KB	Output is correct
33	Correct	2098 ms	78024 KB	Output is correct
34	Correct	432 ms	78024 KB	Output is correct
35	Correct	2126 ms	85844 KB	Output is correct
36	Correct	2279 ms	91640 KB	Output is correct
37	Correct	2260 ms	97580 KB	Output is correct
38	Correct	2194 ms	103444 KB	Output is correct
39	Correct	2392 ms	109180 KB	Output is correct
40	Correct	1645 ms	113820 KB	Output is correct
41	Correct	1925 ms	120520 KB	Output is correct
42	Correct	2297 ms	126300 KB	Output is correct
43	Correct	986 ms	128124 KB	Output is correct
44	Correct	1002 ms	133996 KB	Output is correct
45	Correct	905 ms	140004 KB	Output is correct
46	Correct	838 ms	140004 KB	Output is correct
47	Correct	743 ms	140004 KB	Output is correct
48	Correct	1250 ms	143032 KB	Output is correct
49	Correct	1117 ms	148700 KB	Output is correct

답안 #59335

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 31.0 / 31.0

Subtask #3 65.0 / 65.0

Subtask #1
4.0 / 4.0

Subtask #2
31.0 / 31.0

Subtask #3
65.0 / 65.0