Submission #154649

#	Time	Username	Problem	Language	Result	Execution time	Memory
154649		stefdasca	Ruka (COI15_ruka)	C++14	44 / 100	2066 ms	26116 KiB

ruka

#include<bits/stdc++.h>
#define fi first
#pragma GCC optimize("O3")
#define se second
using namespace std;
int n, q, buk;
char tip;
deque<int>mod;
int poz = 1;
int prefixx[100002], prefixy[100002], ans[100002];
int Le, Ri;
pair<int, int> dir[100002], xx[100002], yy[100002];
vector<vector<int> >aint[2];
void build(int nod, int st, int dr)
{
    aint[0][nod].clear(), aint[1][nod].clear();
    if(st == dr)
    {
        aint[0][nod].push_back(xx[st].se);
        aint[1][nod].push_back(yy[st].se);
        return;
    }
    int mid = (st + dr) / 2;
    build(nod << 1, st, mid);
    build(nod << 1|1, mid+1, dr);
    int pa = 0;
    int pb = 0;
    while(pa < aint[0][nod << 1].size() && pb < aint[0][nod << 1|1].size())
    {
        if(aint[0][nod << 1][pa] <= aint[0][nod << 1|1][pb])
            aint[0][nod].push_back(aint[0][nod << 1][pa]), ++pa;
        else
            aint[0][nod].push_back(aint[0][nod << 1|1][pb]), ++pb;
    }
    while(pa < aint[0][nod << 1].size())
        aint[0][nod].push_back(aint[0][nod << 1][pa]), ++pa;
    while(pb < aint[0][nod << 1|1].size())
        aint[0][nod].push_back(aint[0][nod << 1|1][pb]), ++pb;
    pa = 0;
    pb = 0;
    while(pa < aint[1][nod << 1].size() && pb < aint[1][nod << 1|1].size())
    {
        if(aint[1][nod << 1][pa] <= aint[1][nod << 1|1][pb])
            aint[1][nod].push_back(aint[1][nod << 1][pa]), ++pa;
        else
            aint[1][nod].push_back(aint[1][nod << 1|1][pb]), ++pb;
    }
    while(pa < aint[1][nod << 1].size())
        aint[1][nod].push_back(aint[1][nod << 1][pa]), ++pa;
    while(pb < aint[1][nod << 1|1].size())
        aint[1][nod].push_back(aint[1][nod << 1|1][pb]), ++pb;
}
void rebuild(int start_poz)
{
    mod.clear();
    prefixx[0] = 1; prefixy[0] = 1;
    for(int i = 1; i <= n; ++i)
    {
        ans[i] = ans[i-1];
        if(prefixx[i-1] > 0 && prefixx[i-1] + dir[i].fi < 0)
            ++ans[i];
        if(prefixx[i-1] < 0 && prefixx[i-1] + dir[i].fi > 0)
            ++ans[i];
        if(prefixy[i-1] > 0 && prefixy[i-1] + dir[i].se < 0)
            ++ans[i];
        if(prefixy[i-1] < 0 && prefixy[i-1] + dir[i].se > 0)
            ++ans[i];
        prefixx[i] = prefixx[i-1] + dir[i].fi;
        prefixy[i] = prefixy[i-1] + dir[i].se;
    }
    Le = max(1, start_poz - buk);
    Ri = min(n, start_poz + buk);
    for(int i = Le; i <= Ri; ++i)
        mod.push_back(i);
    for(int i = 1; i <= n - (Ri + 1) + 1; ++i)
    {
        xx[i] = {max(prefixx[Ri + i], prefixx[Ri + i - 1]), min(prefixx[Ri + i], prefixx[Ri + i - 1])};
        yy[i] = {max(prefixy[Ri + i], prefixy[Ri + i - 1]), min(prefixy[Ri + i], prefixy[Ri + i - 1])};
    }
    sort(xx + 1, xx + n - (Ri + 1) + 1 + 1);
    sort(yy + 1, yy + n - (Ri + 1) + 1 + 1);
    if(Ri != n)
        build(1, 1, n - (Ri + 1) + 1);
}
int queryx(int nod, int st, int dr, int L, int R, int threshold)
{
    if(dr < L || st > R)
        return 0;
    if(L <= st && dr <= R)
    {
        int st1 = 0;
        int dr1 = aint[0][nod].size() - 1;
        int ans = -1;
        while(st1 <= dr1)
        {
            int mid = (st1 + dr1) / 2;
            if(aint[0][nod][mid] < threshold)
                ans = mid, st1 = mid + 1;
            else
                dr1 = mid - 1;
        }
        return (ans + 1);
    }
    int mid = (st + dr) / 2;
    return queryx(nod << 1, st, mid, L, R, threshold) + queryx(nod << 1|1, mid+1, dr, L, R, threshold);
}
int queryy(int nod, int st, int dr, int L, int R, int threshold)
{
    if(dr < L || st > R)
        return 0;
    if(L <= st && dr <= R)
    {
        int st1 = 0;
        int dr1 = aint[1][nod].size() - 1;
        int ans = -1;
        while(st1 <= dr1)
        {
            int mid = (st1 + dr1) / 2;
            if(aint[1][nod][mid] < threshold)
                ans = mid, st1 = mid + 1;
            else
                dr1 = mid - 1;
        }
        return (ans + 1);
    }
    int mid = (st + dr) / 2;
    return queryy(nod << 1, st, mid, L, R, threshold) + queryy(nod << 1|1, mid+1, dr, L, R, threshold);
}
int solve()
{
    int start = mod[0] - 1;
    int sol = ans[start];
    int sumx = prefixx[start];
    int sumy = prefixy[start];
    for(int i = 0; i < mod.size(); ++i)
    {
        if(sumx > 0 && sumx + dir[mod[i]].fi < 0)
            ++sol;
        if(sumx < 0 && sumx + dir[mod[i]].fi > 0)
            ++sol;
        if(sumy > 0 && sumy + dir[mod[i]].se < 0)
            ++sol;
        if(sumy < 0 && sumy + dir[mod[i]].se > 0)
            ++sol;
        start = mod[i];
        sumx += dir[mod[i]].fi;
        sumy += dir[mod[i]].se;
    }
    if(Ri != n)
    {
        int st = 1;
        int dr = n - Ri;
        int ans = 0;
        while(st <= dr)
        {
            int mid = (st + dr) / 2;
            if(xx[mid].fi >= -(sumx - prefixx[mod.back()]))
                ans = mid, dr = mid - 1;
            else
                st = mid + 1;
        }
        if(ans != 0)
            sol += queryx(1, 1, n - Ri, ans, n - Ri, -(sumx - prefixx[mod.back()]));
        st = 1;
        dr = n - Ri;
        ans = 0;
        while(st <= dr)
        {
            int mid = (st + dr) / 2;
            if(yy[mid].fi >= -(sumy - prefixy[mod.back()]))
                ans = mid, dr = mid - 1;
            else
                st = mid + 1;
        }
        if(ans != 0)
            sol += queryy(1, 1, n - Ri, ans, n - Ri, -(sumy - prefixy[mod.back()]));
    }
    return sol;
}
void solvegood()
{
    rebuild(poz);
    for(int i = 1; i <= q; ++i)
    {
        cin >> tip;
        if(tip == 'B')
            poz = max(1, poz - 1);
        if(tip == 'F')
            poz = min(poz + 1, n);
        if(tip == 'Q')
            cout << solve() << '\n';
        if(tip == 'C')
        {
            int a, b;
            cin >> a >> b;
            dir[poz] = {a, b};
        }
        if(poz < Le || poz > Ri)
            rebuild(poz);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> dir[i].fi >> dir[i].se;
    cin >> q;
    buk = 1000;
    aint[0].resize(4 * n);
    aint[1].resize(4 * n);
    solvegood();
    return 0;
}

Compilation message (stderr)

ruka.cpp: In function 'void build(int, int, int)':
ruka.cpp:28:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pa < aint[0][nod << 1].size() && pb < aint[0][nod << 1|1].size())
           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:28:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pa < aint[0][nod << 1].size() && pb < aint[0][nod << 1|1].size())
                                            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:35:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pa < aint[0][nod << 1].size())
           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:37:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pb < aint[0][nod << 1|1].size())
           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:41:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pa < aint[1][nod << 1].size() && pb < aint[1][nod << 1|1].size())
           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:41:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pa < aint[1][nod << 1].size() && pb < aint[1][nod << 1|1].size())
                                            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:48:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pa < aint[1][nod << 1].size())
           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:50:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pb < aint[1][nod << 1|1].size())
           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp: In function 'int solve()':
ruka.cpp:135:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < mod.size(); ++i)
                    ~~^~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 35 / 35
• Subtask 3: 0 / 56