Submission #154594

#	Time	Username	Problem	Language	Result	Execution time	Memory
154594		stefdasca	Ruka (COI15_ruka)	C++14	9 / 100	2089 ms	523932 KiB

ruka

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
int n, q;
pair<int, int> dir[100002];
char tip;
int poz = 1, a, b;
int lstque = -1;
void brut()
{
    int ans = 0;
    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 == 'C')
        {
            cin >> a >> b;
            lstque = -1;
            dir[poz] = {a, b};
        }
        if(tip == 'Q')
        {
            if(lstque == -1)
            {
                ans = 0;
                int pa = 1, pb = 1;
                for(int j = 1; j <= n; ++j)
                {
                    if(pa > 0 && pa + dir[j].fi < 0)
                        ++ans;
                    if(pa < 0 && pa + dir[j].fi > 0)
                        ++ans;
                    if(pb > 0 && pb + dir[j].se < 0)
                        ++ans;
                    if(pb < 0 && pb + dir[j].se > 0)
                        ++ans;
                    pa += dir[j].fi;
                    pb += dir[j].se;
                }
                lstque = i;
            }
            cout << ans << '\n';
        }
    }
}
bool is[100002];
deque<int>mod;
int counter = 0;
int prefixx[100002], prefixy[100002];
int ans[100002];
/// 0/1 = x/y, 0/1 = increasing/decreasing, nod
vector<pair<int, int> >aint[2][2][400002];
vector<vector<int> >aint2[2][2][400002];
//ofstream out("ruka.out");
void build2(int B, int F, int R, int nod, int st, int dr)
{
    if(nod != 0)
    {
        vector<int>ro;
        for(int i = st; i <= dr; ++i)
            ro.push_back(aint2[B][F][R][0][i]);
        aint2[B][F][R][nod] = ro;
    }
    if(st == dr)
        return;
    int mid = (st + dr) / 2;
    build2(B, F, R, nod * 2 + 1, st, mid);
    build2(B, F, R, nod * 2 + 2, mid+1, dr);
    sort(aint2[B][F][R][nod].begin(), aint2[B][F][R][nod].end());
}
void build(int nod, int st, int dr)
{
    for(int i = 0; i <= 1; ++i)
        for(int j = 0; j <= 1; ++j)
        {
            aint[i][j][nod].clear();
            aint2[i][j][nod].clear();
            aint2[i][j][nod].resize(4 * (dr - st + 1));
        }
    if(st == dr)
    {
        aint[0][(prefixx[st] <= prefixx[st-1])][nod].push_back({prefixx[st], prefixx[st - 1]});
        aint[1][(prefixy[st] <= prefixy[st-1])][nod].push_back({prefixy[st], prefixy[st - 1]});
        for(int i = 0; i <= 1; ++i)
            for(int j = 0; j <= 1; ++j)
            {
                vector<int>na;
                for(int oo = 0; oo < aint[i][j][nod].size(); ++oo)
                    na.push_back(aint[i][j][nod][oo].se);
                if(!na.size())
                    continue;
                aint2[i][j][nod][0] = na;
                build2(i, j, nod, 0, 0, na.size() - 1);
            }
        return;
    }
    int mid = (st + dr) / 2;
    build(nod << 1, st, mid);
    build(nod << 1|1, mid+1, dr);
    for(int i = 0; i <= 1; ++i)
        for(int j = 0; j <= 1; ++j)
        {
            for(int qu = 0; qu < aint[i][j][nod << 1].size(); ++qu)
                aint[i][j][nod].push_back(aint[i][j][nod << 1][qu]);
            for(int qu = 0; qu < aint[i][j][nod << 1|1].size(); ++qu)
                aint[i][j][nod].push_back(aint[i][j][nod << 1|1][qu]);
            sort(aint[i][j][nod].begin(), aint[i][j][nod].end());
        }
    for(int i = 0; i <= 1; ++i)
        for(int j = 0; j <= 1; ++j)
        {
            vector<int>na;
            for(int oo = 0; oo < aint[i][j][nod].size(); ++oo)
                na.push_back(aint[i][j][nod][oo].se);
            if(!na.size())
                continue;
            aint2[i][j][nod][0] = na;
            build2(i, j, nod, 0, 0, na.size() - 1);
        }
}
void rebuild(int start_poz)
{
    memset(is, 0, sizeof(is));
    mod.clear();
    is[start_poz] = 1;
    mod.push_back(start_poz);
    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;
    }
    if(poz != n)
        build(1, poz + 1, n);
}
int query2(int Bi, int Fr, int Ro, int nod, int L, int R, int st, int dr, int threshold)
{
    if(!aint2[Bi][Fr][Ro][nod].size())
        return 0;
    if(R < st || L > dr)
        return 0;
    if(st <= L && R <= dr)
    {
        int sst = 0;
        int ddr = aint2[Bi][Fr][Ro][nod].size() - 1;
      //  out << Bi << " " << Fr << " " << Ro << " " << nod << " " << L << " " << R << " " << st << " " << dr << " " << threshold << '\n';
      //  for(int i = 0; i < aint2[Bi][Fr][Ro][nod].size(); ++i)
      //      out << aint2[Bi][Fr][Ro][nod][i] << " ";
       // out << '\n';
        if(Fr == 0)
        {
            if(aint2[Bi][Fr][Ro][nod][0] >= threshold)
                return 0;
            int ans = 0;
            while(sst <= ddr)
            {
                int mid = (sst + ddr) / 2;
                if(aint2[Bi][Fr][Ro][nod][mid] < threshold)
                    ans = mid, sst = mid + 1;
                else
                    ddr = mid - 1;
            }
         //   out << 0 << " " << ans << " " << (ans + 1) << '\n';
            return (ans + 1);
        }
        else
        {
            if(aint2[Bi][Fr][Ro][nod].back() <= threshold)
                return 0;
            int ans = ddr + 1;
            while(sst <= ddr)
            {
                int mid = (sst + ddr) / 2;
                if(aint2[Bi][Fr][Ro][nod][mid] > threshold)
                    ans = mid, ddr = mid - 1;
                else
                    sst = mid + 1;
            }
           // out << aint2[Bi][Fr][Ro][nod].size() << " " << ans << " " << (aint2[Bi][Fr][Ro][nod].size() - ans) << '\n';
            return (aint2[Bi][Fr][Ro][nod].size() - ans);
        }
    }
    int mid = (L + R) / 2;
    int ro = query2(Bi, Fr, Ro, nod * 2 + 1, L, mid, st, dr, threshold);
    int se = query2(Bi, Fr, Ro, nod * 2 + 2, mid + 1, R, st, dr, threshold);
    return ro+se;
}
int query(int nod, int L, int R, int st, int dr, int mx, int my)
{
    if(R < st || L > dr)
        return 0;
    if(st <= L && R <= dr)
    {
       // out << nod << " " << L << " " << R << " " << st << " " << dr << " " << mx << " " << my << '\n';
        int sool = 0;
        if(aint[0][0][nod].size())
        {
            int st = 0;
            int dr = aint[0][0][nod].size() - 1;
            int ans = 0;
            if(aint[0][0][nod].back().fi >= mx)
            {
                while(st <= dr)
                {
                    int mid = (st + dr) / 2;
                    if(aint[0][0][nod][mid].fi >= mx)
                        ans = mid, dr = mid - 1;
                    else
                        st = mid + 1;
                }
            //    out << " a " << 0 << " " << 0 << " " << nod << " " << ans << '\n';
                sool += query2(0, 0, nod, 0, 0, aint[0][0][nod].size() - 1, ans, aint[0][0][nod].size() - 1, mx);
             //   out << sool << '\n';
            }
        }
        if(aint[1][0][nod].size())
        {
            int st = 0;
            int dr = aint[1][0][nod].size() - 1;
            int ans = 0;
            if(aint[1][0][nod].back().fi >= my)
            {
                while(st <= dr)
                {
                    int mid = (st + dr) / 2;
                    if(aint[1][0][nod][mid].fi >= my)
                        ans = mid, dr = mid - 1;
                    else
                        st = mid + 1;
                }
              //  out << " a " << 1 << " " << 0 << " " << nod << " " << ans << '\n';
                sool += query2(1, 0, nod, 0, 0, aint[1][0][nod].size() - 1, ans, aint[1][0][nod].size() - 1, my);
              //  out << sool << '\n';
            }
        }
        if(aint[0][1][nod].size())
        {
            int st = 0;
            int dr = aint[0][1][nod].size() - 1;
            int ans = 0;
          //  for(int i = 0; i < aint[0][1][nod].size(); ++i)
           //     cout << aint[0][1][nod][i].fi << " ";
           // cout << '\n';
            if(aint[0][1][nod][0].fi <= mx)
            {
                while(st <= dr)
                {
                    int mid = (st + dr) / 2;
                    if(aint[0][1][nod][mid].fi <= mx)
                        ans = mid, st = mid + 1;
                    else
                        dr = mid - 1;
                }
              //  out << " a " << 0 << " " << 1 << " " << nod << " " << ans << '\n';
                sool += query2(0, 1, nod, 0, 0, aint[0][1][nod].size() - 1, 0, ans, mx);
              //  out << sool << '\n';
            }
        }
        if(aint[1][1][nod].size())
        {
            int st = 0;
            int dr = aint[1][1][nod].size() - 1;
            int ans = 0;
            if(aint[1][1][nod][0].fi <= my)
            {
                while(st <= dr)
                {
                    int mid = (st + dr) / 2;
                    if(aint[1][1][nod][mid].fi <= my)
                        ans = mid, st = mid + 1;
                    else
                        dr = mid - 1;
                }
              //  out << " a " << 1 << " " << 1 << " " << nod << " " << ans << '\n';
                sool += query2(1, 1, nod, 0, 0, aint[1][1][nod].size() - 1, 0, ans, my);
               // out << sool << '\n';
            }
        }
        return sool;
    }
    int mid = (L + R) / 2;
    int ans1 = query(nod << 1, L, mid, st, dr, mx, my);
    int ans2 = query(nod << 1|1, mid + 1, R, st, dr, mx, my);
    return ans1 + ans2;
}
int solve(int start_poz)
{
    int sol = 0;
    int sumx = 0;
    int sumy = 0;
    int start = start_poz - 1;
    sol = ans[start];
    sumx = prefixx[start];
    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;
    }
  //  out << "ince " << start_poz << " " << poz + 1 << " " << n << " " << sumx << " " << prefixx[mod.back()] << " " << sumy << " " << prefixy[mod.back()] << '\n';
    if(mod.back() < n)
        sol += query(1, start_poz + 1, n, mod.back() + 1, n, -(sumx - prefixx[mod.back()]), -(sumy - prefixy[mod.back()]));
    return sol;
}
void solvegood()
{
    int start_poz = 1;
    rebuild(start_poz);
    int ans = 0;
    int buk = sqrt(q);
    for(int i = 1; i <= q; ++i)
    {
        cin >> tip;
        if(tip == 'B')
        {
            poz = max(1, poz - 1);
            if(!is[poz])
            {
                is[poz] = 1;
                if(mod.empty() || poz > mod.back())
                    mod.push_back(poz);
                else
                    mod.push_front(poz);
                if(mod.size() >= buk)
                    start_poz = poz, rebuild(start_poz);
            }
        }
        if(tip == 'F')
        {
            poz = min(poz + 1, n);
            if(!is[poz])
            {
                is[poz] = 1;
                if(mod.empty() || poz > mod.back())
                    mod.push_back(poz);
                else
                    mod.push_front(poz);
                if(mod.size() >= buk)
                    start_poz = poz, rebuild(start_poz);
            }
        }
        if(tip == 'Q')
            cout << solve(start_poz) << '\n';
        if(tip == 'C')
        {
            cin >> a >> b;
            dir[poz] = {a, b};
            if(!is[poz])
            {
                is[poz] = 1;
                if(mod.empty() || poz > mod.back())
                    mod.push_back(poz);
                else
                    mod.push_front(poz);
                if(mod.size() >= buk)
                    start_poz = poz, rebuild(start_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;
    if(1LL * n * q <= 300000000)
        brut();
    else
        solvegood();
    return 0;
}

Compilation message (stderr)

ruka.cpp: In function 'void build(int, int, int)':
ruka.cpp:93:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int oo = 0; oo < aint[i][j][nod].size(); ++oo)
                                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:108:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int qu = 0; qu < aint[i][j][nod << 1].size(); ++qu)
                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:110:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int qu = 0; qu < aint[i][j][nod << 1|1].size(); ++qu)
                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:118:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int oo = 0; oo < aint[i][j][nod].size(); ++oo)
                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp: In function 'int solve(int)':
ruka.cpp:310:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < mod.size(); ++i)
                    ~~^~~~~~~~~~~~
ruka.cpp: In function 'void solvegood()':
ruka.cpp:348:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(mod.size() >= buk)
                    ~~~~~~~~~~~^~~~~~
ruka.cpp:362:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(mod.size() >= buk)
                    ~~~~~~~~~~~^~~~~~
ruka.cpp:379:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(mod.size() >= buk)
                    ~~~~~~~~~~~^~~~~~
ruka.cpp:333:9: warning: unused variable 'ans' [-Wunused-variable]
     int ans = 0;
         ^~~

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