oj.uz

답안 #76732

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
76732 2018-09-16T18:19:39 Z kdh9949 운세 보기 2 (JOI14_fortune_telling2) C++17
0 / 100
 14 ms 12792 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define all(v) (v).begin(),(v).end()

const int N = 200005, sz = 262144;
int n, m, a[N], b[N], c[N], t[N], x[N];
ll r;

struct Seg{
    vector<int> v[2 * sz];
    int u(int x, int y){
        for(x += sz; x; x >>= 1) v[x].push_back(y);
    }
    int m(int s, int e){
        int r = 0;
        for(s += sz, e += sz; s <= e; s >>= 1, e >>= 1){
            if( s & 1){ if(!v[s].empty()) r = max(r, v[s].back()); s++; }
            if(~e & 1){ if(!v[e].empty()) r = max(r, v[e].back()); e--; }
        }
        return r;
    }
    int c(int s, int e, int x){
        int r = 0;
        for(s += sz, e += sz; s <= e; s >>= 1, e >>= 1){
            if( s & 1){ r ^= int(v[s].end() - lower_bound(all(v[s]), x)); s++; }
            if(~e & 1){ r ^= int(v[e].end() - lower_bound(all(v[e]), x)); e--; }
        }
        return r & 1;
    }
} S;

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++){
        scanf("%d%d", a + i, b + i);
        if(a[i] > b[i]){ c[i] = 1; swap(a[i], b[i]); }
    }
    for(int i = 1; i <= m; i++){
        scanf("%d", t + i);
        x[i - 1] = t[i];
    }
    sort(x, x + m);
    for(int i = 1; i <= m; i++){
        t[i] = int(lower_bound(x, x + n, t[i]) - x + 1);
        S.u(t[i], i);
    }
    for(int i = 1; i <= n; i++){
        int p = int(lower_bound(x, x + n, a[i]) - x + 1);
        int q = int(lower_bound(x, x + n, b[i]) - x);
        int t = S.m(p, q);
        r += (S.c(q + 1, m, t + 1) ^ (!t & !c[i])) ? a[i] : b[i];
    }
    printf("%lld\n", r);
}

Compilation message

fortune_telling2.cpp: In member function 'int Seg::u(int, int)':
fortune_telling2.cpp:15:5: warning: no return statement in function returning non-void [-Wreturn-type]
     }
     ^
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:35: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:37:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", a + i, b + i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", t + i);
         ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 12792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 12792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 12792 KB Output isn't correct
2 Halted 0 ms 0 KB -