제출 #723758

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
723758		kkts	운세 보기 2 (JOI14_fortune_telling2)	C++14	35 / 100	162 ms	27632 KiB

fortune_telling2

#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int fw[N], a[N], b[N], c[N], t[4 * N], m;
vector<int> X[N];
void upd(int id) {
    for(id; id <= m; id += id & (-id)) fw[id] ^= 1;
}
int get(int id) {
    int ans = 0;
    for(id; id >= 1; id -= id & (-id)) ans ^= fw[id];
    return ans;
}
bool cmp(int x, int y) {
    return (max(a[x], b[x]) < max(a[y], b[y]));
}
int merge(int i, int j) {
    return (max(a[i], b[i]) >= max(a[j], b[j]) ? i : j);
}
void build(int u, int l, int r) {
    if(l == r) {
        t[u] = (X[l].size() ? X[l].back() : 0);
        return;
    }
    int mid = (l + r) / 2;
    build(2 * u, l, mid); build(2 * u + 1, mid + 1, r);
    t[u] = merge(t[2 * u], t[2 * u + 1]);
}
void rem(int u, int id, int l, int r)  {
    if(l > id || r < id) return;
    if(l == r) {
        X[l].pop_back();
        t[u] = (X[l].size() ? X[l].back() : 0);
        return;
    }
    int mid = (l + r) / 2;
    rem(2 * u, id, l, mid); rem(2 * u + 1, id, mid + 1, r);
    t[u] = merge(t[2 * u], t[2 * u + 1]);
}
int get(int u, int st, int en, int l, int r) {
    if(l > en || r < st) return 0;
    if(st <= l && r <= en) return t[u];
    int mid = (l + r) / 2;
    return merge(get(2 * u, st, en, l, mid), get(2 * u + 1, st, en, mid + 1, r));
}
main(){
    int n, k;
    cin >> n >> k;
    vector<int> x;
    vector<int> A(n + 1), B(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        A[i] = a[i]; B[i] = b[i];
        x.push_back(a[i]);
        x.push_back(b[i]);
    }
    for(int i = 1; i <= k; i++) {
        cin >> c[i];
        x.push_back(c[i]);
    }
    sort(x.begin(), x.end());
    x.erase(unique(x.begin(), x.end()), x.end());
    for(int i = 1; i <= n; i++)
    a[i] = lower_bound(x.begin(), x.end(), a[i]) - x.begin() + 1,
    b[i] = lower_bound(x.begin(), x.end(), b[i]) - x.begin() + 1,
    X[min(a[i], b[i])].push_back(i);
    for(int i = 1; i <= x.size(); i++) sort(X[i].begin(), X[i].end(), cmp);
    build(1, 1, x.size());
    m = x.size();
    int ans = 0;
    for(int i = k; i >= 0; i--) {
        c[i] = lower_bound(x.begin(), x.end(), c[i]) - x.begin() + 1;
        while(true) {
            int id = get(1, 1, (!i ? m : c[i]), 1, m);
            if(max(a[id], b[id]) > (!i ? 0 : c[i])) {
                if(i) ans += (get(min(a[id], b[id])) ? min(A[id], B[id]) : max(A[id], B[id]));
                else ans += (get(min(a[id], b[id])) == 0 ? A[id] : B[id]);
                rem(1, min(a[id], b[id]), 1, m);
            } else break;
        }
        upd(1);
        upd(c[i] + 1);
    }
    cout << ans;
}

컴파일 시 표준 에러 (stderr) 메시지

fortune_telling2.cpp: In function 'void upd(long long int)':
fortune_telling2.cpp:11:9: warning: statement has no effect [-Wunused-value]
   11 |     for(id; id <= m; id += id & (-id)) fw[id] ^= 1;
      |         ^~
fortune_telling2.cpp: In function 'long long int get(long long int)':
fortune_telling2.cpp:15:9: warning: statement has no effect [-Wunused-value]
   15 |     for(id; id >= 1; id -= id & (-id)) ans ^= fw[id];
      |         ^~
fortune_telling2.cpp: At global scope:
fortune_telling2.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   50 | main(){
      | ^~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:71:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int i = 1; i <= x.size(); i++) sort(X[i].begin(), X[i].end(), cmp);
      |                    ~~^~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 0 / 65