oj.uz

답안 #123964

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
123964 2019-07-02T10:14:52 Z arnold518 Bubble Sort 2 (JOI18_bubblesort2) C++14
0 / 100
 21 ms 3444 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 5e5;
const int MAXQ = 5e5;
const ll NEGINF = -1e17;

int N, Q, S;
vector<ll> A, X, V, comp;
vector<int> ans;

ll getcomp(ll x)
{
    return lower_bound(comp.begin(), comp.end(), x)-comp.begin()+1;
}

struct SEG
{
    int N;
    vector<ll> tree, lazy;
    SEG(int N) : N(N), tree(4*N+10, NEGINF), lazy(4*N+10, 0ll) { }

    void busy(int node, int tl, int tr)
    {
        if(lazy[node]==0) return;
        tree[node]+=lazy[node];
        if(tl!=tr) lazy[node*2]+=lazy[node], lazy[node*2+1]=lazy[node];
        lazy[node]=0;
    }

    void update_change(int node, int tl, int tr, int pos, ll val)
    {
        busy(node, tl, tr);
        if(tl==tr)
        {
            tree[node]=val;
            return;
        }
        int mid=tl+tr>>1;
        if(pos<=mid) update_change(node*2, tl, mid, pos, val);
        else update_change(node*2+1, mid+1, tr, pos, val);
        tree[node]=max(tree[node*2], tree[node*2+1]);
    }

    void update_range(int node, int tl, int tr, int l, int r, ll val)
    {
        //printf("!!!!!%d %d %d %d %d %lld\n", node, tl, tr, l, r, val);
        busy(node, tl, tr);
        if(tr<l || r<tl) return;
        if(l<=tl && tr<=r)
        {
            tree[node]+=val;
            if(tl!=tr) lazy[node*2]+=val, lazy[node*2+1]+=val;
            return;
        }
        int mid=tl+tr>>1;
        update_range(node*2, tl, mid, l, r, val);
        update_range(node*2+1, mid+1, tr, l, r, val);
        tree[node]=max(tree[node*2], tree[node*2+1]);
    }

    void debug(int node, int tl, int tr)
    {
        if(tl==tr)
        {
            printf("(%d : %lld) ", tl, tree[node]);
            return;
        }
        int mid=tl+tr>>1;
        debug(node*2, tl, mid);
        debug(node*2+1, mid+1, tr);
    }

    ll query()
    {
        busy(1, 1, N);
        return tree[1];
    }
};

struct BIT
{
    int N;
    vector<ll> tree;
    BIT(int N) : N(N), tree(N+10) {}
    void update(int i, int val) { for(; i<=N; i+=(i&-i)) tree[i]+=val; }
    ll query(int i) { ll ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
};

vector<int> countScans(vector<int> a, vector<int> x, vector<int> v)
{
    int i, j;
    N=a.size(); Q=x.size();
    for(i=0; i<a.size(); i++) A.push_back(a[i]*N+i), comp.push_back(a[i]*N+i);
    for(i=0; i<x.size(); i++) V.push_back(v[i]*N+x[i]), comp.push_back(v[i]*N+x[i]);
    for(i=0; i<v.size(); i++) X.push_back(x[i]);

    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    S=comp.size();

    for(i=0; i<N; i++) A[i]=getcomp(A[i]);
    for(i=0; i<Q; i++) V[i]=getcomp(V[i]);

    SEG seg(S);
    BIT bit(S);

    for(i=0; i<N; i++) bit.update(A[i], 1);
    for(i=0; i<N; i++) seg.update_change(1, 1, S, A[i], i-bit.query(A[i]-1));

    //for(i=0; i<N; i++) printf("%lld ", A[i]); printf("\n");
    //seg.debug(1, 1, S); printf("\n");

    for(i=0; i<Q; i++)
    {
        ll pos=X[i], bef=A[pos], aft=V[i];
        bit.update(bef, -1);
        bit.update(aft, 1);

        if(bef<aft)
        {
            if(bef+1<=aft-1) seg.update_range(1, 1, S, bef+1, aft-1, 1);
            seg.update_change(1, 1, S, bef, NEGINF);
            seg.update_change(1, 1, S, aft, pos-bit.query(aft-1));
        }
        else
        {
            if(aft+1<=bef-1) seg.update_range(1, 1, S, aft+1, bef-1, -1);
            seg.update_change(1, 1, S, bef, NEGINF);
            seg.update_change(1, 1, S, aft, pos-bit.query(aft-1));
        }

        ans.push_back(seg.query());

        A[pos]=V[i];

        //printf("%lld %lld %lld\n", pos, bef, aft);
        //for(j=0; j<N; j++) printf("%lld ", A[j]); printf("\n");
        //seg.debug(1, 1, S); printf("\n");
    }
    return ans;
}

Compilation message

bubblesort2.cpp: In member function 'void SEG::update_change(int, int, int, int, ll)':
bubblesort2.cpp:44:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
bubblesort2.cpp: In member function 'void SEG::update_range(int, int, int, int, int, ll)':
bubblesort2.cpp:61:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
bubblesort2.cpp: In member function 'void SEG::debug(int, int, int)':
bubblesort2.cpp:74:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:99:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<a.size(); i++) A.push_back(a[i]*N+i), comp.push_back(a[i]*N+i);
              ~^~~~~~~~~
bubblesort2.cpp:100:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<x.size(); i++) V.push_back(v[i]*N+x[i]), comp.push_back(v[i]*N+x[i]);
              ~^~~~~~~~~
bubblesort2.cpp:101:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<v.size(); i++) X.push_back(x[i]);
              ~^~~~~~~~~
bubblesort2.cpp:97:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

Subtask #1
0 / 17.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

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