Submission #1142219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142219		kfhjad	Examination (JOI19_examination)	C++20	22 / 100	3097 ms	142128 KiB

examination

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int INF = INT_MAX;

struct Fenwick2D
{
    int N;
    vector<map<int, int>> comp;
    vector<vector<int>> f;
    int tot = 0;
    
    Fenwick2D(int n, auto& a, auto& queries) : N(n + 1), comp(n + 1), f(n + 1)
    {
        for (auto& [x, y, z] : a)
            for (int i = y; i < N; i += i & -i)
                comp[i][z];
        
        for (auto& [x, y, z, _] : queries)
        {
            for (int i = y - 1; i > 0; i -= i & -i)
                comp[i][INF];

            for (int i = N - 1; i > 0; i -= i & -i)
                comp[i][z - 1];
                
            for (int i = y - 1; i > 0; i -= i & -i)
                comp[i][z - 1];
        }
        
        for (auto& m : comp)
            for (int cnt = 1; auto& [k, v] : m)
                v = cnt++;
            
        for (int i = 0; i < N; ++i)
            f[i].resize(comp[i].size() + 1);
    }
    
    void update(int i, int y)
    {
        ++tot;
        for (; i < N; i += i & -i)
            for (int z = comp[i][y]; z < (int)f[i].size(); z += z & -z)
                ++f[i][z];
    }
    
    int query(int i, int y)
    {
        int res = 0;
        for (; i > 0; i -= i & -i)
            for (int z = comp[i][y]; z > 0; z -= z & -z)
                res += f[i][z];
        
        return res;
    }
};

int main()
{
    cin.tie(NULL) -> sync_with_stdio(false);
    int N, Q;
    cin >> N >> Q;
    
    map<int, int> comp;
    vector<array<int, 3>> a(N);
    for (auto& [x, y, z] : a)
    {
        cin >> x >> y;
        z = x + y;
        comp[y];
    }
    
    sort(a.rbegin(), a.rend());
    
    vector<array<int, 4>> queries(Q);
    for (int i = 0; i < Q; ++i)
    {
        int x, y, z;
        cin >> x >> y >> z;
        queries[i] = {x, y, z, i};
        comp[y];
    }
    
    sort(queries.rbegin(), queries.rend());
    
    for (int cnt = 1; auto& [k, v] : comp)
        v = cnt++;
    
    for (auto& [x, y, z] : a)
        y = comp[y];
    
    for (auto& [x, y, z, i] : queries)
        y = comp[y];
    
    Fenwick2D f(comp.size(), a, queries);
    
    vector<int> ans(Q);
    int at = 0;
    for (auto& [x, y, z, i] : queries)
    {
        for (; at < (int)a.size() && a[at][0] >= x; ++at)
            f.update(a[at][1], a[at][2]);
        
        ans[i] = f.tot - f.query(y - 1, INF) - f.query(f.N - 1, z - 1) + f.query(y - 1, z - 1);
    }
    
    for (int i : ans)
        cout << i << '\n';
	
    return 0;
}                              /*****************************=
                            -+**********************************= 
                        :-*****************************************+:
                    ..:*************+=+*******************************=.
                 ..-==*****************+=-+*****************************+.
               ..-=***********************+--+****************************= 
               :+**************#*#**********+--+***************************-  .=--=.  
             .+*********************#*********+--****************************++++----:        
            -+***********************##*********--+********************************+--=.      
           =****=**********************#*********+-=***************************#*****+--=     
         .=****+***********************************-=*********************#*****##*****=-=.   
        :=*****=************************************=-*****************#******#####*****=-=.  
       .=**+***=**************************#**********==***********##*******#**######*****+-=. 
       +***=***+***************************#**********-+*****####********#*****#####******+-=:
      =+**=****+****************#**********************-*####*********##***#*#######*******+-=.
     .=*#*=****=****************#***********#**********++#*********###****#*#*######********+-=. 
     =**#++****=***#******#******#***********#**********=*******####****##**#########********=-= 
    .=*##=****#=***#*******#*****#*#*********#*#********+****#####****###**#*######%#*********-==
    -*###=**###+*#*#######*##*######*######**##########*#*####*....-#########%##%##%##########=-*.
    =*###+######+############################################=..+=-+.########%##%##%##########*-+* 
    +###*+######**#################%##########%###########%#*..=-+===-######%###+##%###########-+#.
   .+###**#######+###%############%#%#########%###########%#...=*:.=:.#####%#%%#+##%###########=+#+
  .-+#%#**#######%=###%#############%%######%#%%##########*...+===+...####%%%%% *%%############=+##
  .=*#%#*+#######%%+##%%###########%#%%%######%%#%########=...====+..####%%%%%: *%%############=*##
  .+*#*##+###%###%%%%##%%##########*##%%%####%%%#%#######%*=-..====:####%%%%%=  #%%############=###-
  .+*#=#-=#####%#%%%####%%%########+*###%%%##%%%#%#######%*==:==+-.*##%%%%%%+   #%%###########*=###+
  :=##=#-+####%%#%%%#**##%%%#######+++#*+%*%%%%%#%%########=.-=....##%%%%%%*....%%%#####%#####+=####-
   .#*.#--*#####%#%%#****##%%#####+-===#+=**+%%%#%%########=......+%%%%%%%+     %%######%#####=*####.
    #* *+.*####%%%%%#++++- :*%%###+.....--..*==#%%%########==-:::=%%%%%%%-      %%######%#####=#####.
    -# .%.=####%%%%%#++=*......:##*.......-..-==%%%#####%##=#%%%%%%%%%%#        #%######%####*=###%#
     *. +-.####%%%%%%===.=....-:.*#...........-=%%%#######*==*@%%%%%%%*         #%######%####+*###%#
         *.:###%%%%%%-.....=......*:...........-%%%######%+*==*#%%%%%#          +%######%####=####%#.
          =.=###%%%%%:.............:............#*%%####*#*=====%@%%%           :%#####%%####+######:
           .=%##%%%%%*.............:............#*%%####+#+======%#%*        .:-=%%%%%%%%###+#####+#-
            .%%##%%%-*-..............::::.......#+%%####+#=====-...#:  :*%%%%%%%%%%%%%%%%###*#####=#=
            .####%%%:.:-.......--...............#=#%###+*#====-...:*%%%%%%%%%%%%%%%%%%%%%%########:#+
             *-#%#%%-  -..........:----........:*=#%##%=*+=====#%%%%%%%%%%%%%%%%%%%%%%%%%%########:#*
             =*.%%%%=   .:........:::..........=.=####+=#=*%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%###.*#
              #..%%%#.    -....................-:+###%*%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*#
              +- :%%%#+     =..................===%##%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%#:.
              .#. =%% .*=     -.............:+#%%%%#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+.
               .*  *%-         .-........:*%%%%%%%#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@%%%%%%#.
                .=. ##         ..-:..:#%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@%%%:
                  ..=*-    .*@@@@@%%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%-.
                           #@%%%%%%%%%%%%%%%%%%%@%%%@@@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*:.
                           *@%%%%%%%%%%%%%%%%%%%%%@@@%@@@@%%%%%@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%=:
                           :@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%#:
                           .%@%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%:
                           .-%@%%%%%%%@@%%%%%%%%%%%%%%@@@@@@@@@@@%%%%%%%%%%%%@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%@-
                           ..#%@%%%%%@%%%%%%%%%%%%@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%:
                             .%@%%%%@%%%%%%%%%%%@@@@@@@@@%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%::
                             .:@@%@%%%%%%%%%%%%@@@@@@@@%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%@@@%%%%%%%%%%%%%%%%%%-::
                             .*@%%%%%%%%%%%%%@@@@@@@@@%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%@%%@@%%%%%%%%%%%%%%%%@=:
                             -@%@@@@@@@@@@@@@@@@@@%@%%%%%%@@%@@%%%%@@@%%%%%%%%%%%%%%%%%%%%@@@%@@@@@@@@@@@@@+:
                             %@@@@@@@@@@@@@@@@@@@@%%%%%%@@@@@%%%%%@@@@%%%%%%%%%%%%%%%%%%%%%@@@@@@@@@@@@@@@+-
                             *@@@@@@@@@@@@@@@@@@%%%%%%%%@@@@%%%%%@@@@@@%%%%%%%%%%%%%%%%%@%%%@@@@@@@@@@@@@@#-
                             :%@@@@@@@@@@@@@@@@%%%%%%%%@@@@%%%%@@@@@@@@%%%%%%%%%%%%%%%%%@%%%%@@@@@@@@@@@@*%-
                              :#@@@@@@@@@@@@@%%%%%%%%%@@@@%%%%%@@@@@@@@@%%%%%%%%%%%%%%%%%@%%%@@@@@@@@@@@+-%*
                               :-@@@@@@@@@%%%%%%%%%%%@@@@@%%%%@@@@@@@@@@%%%%%%%%%%%%%%%%%@@%%%@@@@@@@@@#--*%
                                 :=@@@@@@%%%%%%%%%%%@%@@@@%%%@@@@@@@@@@@@%%%%%%%%%%%%%%%%%@@%%%@@@@@@@%%---%+
                                -:-@@@@%%%%%%%%@%%%@@%@@@%%%@@@@@@@@@@@@@%%%%%%%%%%%%%%%%%@@@%%@@@@@%%%%=--*%
                                -=@@@%%%%%%%%%@@%%@@%@@@@%%@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%%@@@%%%@@%%%%%%+--=%+
                               -=@@%%%%%%%%%%@@%%@@%%@@@@%@@@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%%@@@%%@##%%%%%#---*%-
                              -+@%%%%%%%%%%%@@@%@@%%@@@@@%@@@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%%@@@@%@##%%%%%%====%*/

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57