제출 #1271166

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271166		kiritogaming	Examination (JOI19_examination)	C++20	20 / 100	269 ms	15080 KiB

examination

//                                                  -....:-                                             
//                                                =...+++=---              -=   +.*                     
//                                                ...       ==           -++  :++*                      
//                                                :.=        *#         +=*#%.:*=%                      
//                                                =.:                 *#%%%%-=*%-                       
//                                                 *:+               %*%%%%+%%%%*%-+    +               
//                                                   -=*     *#####*##%%%%%%%%%%==%% =::+#              
//                                                     ==+   #########*=+@%%%%%%%%%**:+=*               
//                                                        ==***+*#%%#%***+=@@*%%%%#+-*=%                
//                                                      +:..:-==-----*##***+*%%%%*%@*%%                 
//                                                    =........-==--:.-%*****-@=-@@%%%%%%               
//                                                  @:.......-....:.:-+-%+%+#%***-##=%                  
//                                                 *:.:....:.....:....:-=%*@#--*+*=+%                   
//                                                =.-::...:...........::-+%%%+-++*#%#                   
//                                            +::-=+-...:.........:...:::=+#@#**#####                   
//                                              *-:.....:...:-.......::::=:+#@#:**##*                   
//                                         ++==.=:::::...==-::..:.....:::-:-=%%%##*##                   
//                                          :.:.:..:---+#%*:.-.:-.:.:::.:--:+   %*#*#*                  
//                                         --==---..=:-:-:-+:..:.-.:-::--:-=-    ###**                  
//                                          +----.-==:+..:....:.:#*+-::-:::=-+    ###%                  
//                                              ----=+=-........-::::==:--.:+-    %%#%                  
//                                            --+  +:=:+:...........+=:-.:*:-+    %%#      author: kiritogaming             
//                                                  -..-#+........+:--=:.=-=-     @%%                   
//                                                 .:::=%%*+-*%*+-:-:::==        %%                     
//                                               % +.*@=@##@+=@@-.::=%#%##      %%                      
//                                             **++###+=#+%@@%###+.##%##%#     %                        
//                                            #%#*##%##*%##%%#+++*##%###%%#               <3 Furina              
//                                          *#+#######*#%%#%@%=*+*+=#####%#                             
//                                        #*%%#*#@%%+*#%%#%%%%*=#=#**%%##@*                  %@         
//                                      ##%%%%#%@@**##*@@#****#*#%%@@@%%*#*##        =-%%@ %%%%%@%      
//                                     %%%%%%%%%@@%%@@@%##*#++%%%%%@%####@%+# =-.::..*%%%%@*.-.-:=**#@  
//                            **     %*%%%%%%@%%%@@@@%%%###@%%%%%%%%%%%####%# ::-=%###%%+::.::::-=-:=   
//                           #*#   +%%%%%%%%%@%%%@%%%%%%%%##%%%%@%@@ @%%%%##%**.:-=+%%%@-*:.-:::.-...-  
//     -===+*               *=+-##%####%%@%@ %=@%%%#+%+###%%%%@@@%    @%%%%%#%#++#@@@@#%%#*--:=::--:-#  
//    ==--:-..*           #++=.-%###%%@@@@   ##%%%+=%#####%%@@@%%       %%######**@@@@%%%@%%%%%%%#==-..+
//   -.--.-+**.=        #***#--##%%%%%%@@== ++#+--++%-###%@@@@%  ####@   @%#####%+***++@#+# %%%%      ==
//   :-*=..=+===     @*********++%*+@   +++--=+==*#*%%%%%%%%@%*#####**    @%##%%%#++++**+               
//   -.+=-::-===%%##%@%#%%%%@@@#***%@  ++=#+=:-+=*%%%#%%%%%%@++*+++++#      @%@@@%# ***#                
// --: ===+-.==+*=##%%@@%%%%%%#%      %#++===#%#.*%%%%%%%%%%%%%*++++*                                   
// -=:=-.--:-*=% #-##%%@@@%#@          =*#%+%#%###**%@%%%%%%@%%%++****                                  
// :-===:=-*---+*#*#*###%@        =-+++-+#=@*%%%%%%%%%@%%@%%%%%%#%+*%                                   
//   -==---:+:=:#*#%@###%++       *+:=#%#=#%%%%%%%##%*@@@#%%%%%%###%+====--                             
//       ---**=##%@@====%====     #*+#**#=%######%+*%@@@@%%%%%%%%###%@ =====*+                          
//          ##%%*%-=======-=== -:-=*=#=%###%######%%%%##%%%%%%%%%%%####% *------+                       
//         #%@%=-:@%=-====- =-+++*+--#@##%%########%%%#=#@%%%%%%@%%@##*###*==:--:*                      
//        %%@ #%::=*   ====*  -*:-% %**###########%%%#@@@%#@##@%@@@@%%*#*%####*+::*=                    
//        %@  #%#::-+    -:=  =-   ##-+%%%######%%@@@@@%%%#+*#**@%%####**#@%###%@%#++---=               
//           =+@#-=-=*=====+-#== @##%#%%%@%%%%%%%%%%%%%%%%%%%#+%@%#####-#**%%####%%@@@%=---             
//          -++ =*=++*====---%+##%%#%%%%%%%%%%%%%%%%%%%%%%%%%#+#%#######-=+=##%#%%%%%%%   --            
//          =+=++=+-=*+:++%%:=%%%%%%%@%%%%%%%%%%%@%#:........:+##%#****#*-*=*##%%%%%%%%    =            
//          -+=++:-=-.++*=+%-+%%%%%%%*+.........:--...........-#:********-+=*####%%%#%                  
//           +=++:#+===+*=-=%%%%%%%%#*#*:.....:+%####***####*#++%*******+=*=######%@@%                  
//           +=+ +***=+**:--=+%%%%%####%%##%##%%#=#%#*++++=--:=+#******==*=*%%%%%%%%%%%                 
//            ==    #=+==-=:-- -*%%####+..........=...........=+=******==+#%%%%%%%%%%%@                 
//             =:   ##+:=*-=- :-*%%%####..........-..........:+==******=+*+%%%%%%%%%%                   
//              =---::-+=+-#  -==%%%%###*........:-...........+.*=+**+++*+%%%%%%%%@%%                   
//                :::--*-=%%% --#*######%-.....:::-............:+=++++*+*%#%%%%@@@@%%                   
//                      -:=#==-+****##%##%:...:::::............==+=+***@%%%%%%%@@@@%%                   
//                     -=*+=++=+++*#%%@@@@#::::::::............++-+**@%%%%%%%%%%%%@@@                   
//                   -----+++*++*##%%%@@@@@=::::::::..........+*+*+*%%%%%%%%%@%%%%%@@%                  
//                   ----==+=+####%%%@@@@@@@::::::::..........##%**#%%%%%%%%@@%%%%%%%                   
//                     +==----=##%%@%%%%@@@@+::::::-.........=#####%%%%%%%%@@@%%%%%%%                   
//                       #####*#%@%%%%%@@@@@@::::::-.........%####%%%%%@@%%%%@%%%%%                     
//                          @%%##@%%%%@@@@@@@@:::::-........:@@@@%%%%@@@%%%%%@%%@                       
//                        %%%%%#+##%%@@@@@@@@@=::::=........#@@@@@@%%%@@%%%%%@@                         
//                     @%%%%%%%***#%%%%@@@%%%%%::::=........%%@@@%%%%%@@%%%%%@@                         
//                   %#%%##*=*%*++-%@@%%%%%%%%%+:::-.......-%%%@@%%%%%%%%%%%%@%                         
//               @%#%%%%%%%%%%%%%=-=%%%%%%%%%%%%-:::.......-%%%@@%%%%%@%%%%%%                           
//           @%##%%#%%%%%%%%%%%##%==*#%%%%%%%%%@@*:-:....:..#%%@@%%%%%@%%%%                             
//        %%#%%%%#%%%%%%%%%%%%%%%%#--%%%%@@@@@@@%%%-.:......--%@%%%%%%@@@                               
//      %%%%%%%%%%%%%%%%%%%%%%%%%%%*--@  @@@@@%%%%%%-........=:@%%@@@%@@%                               
//          %%%%%%%%%%%%%%%%%%%%%%@ =-- @@@@@%%%%%%%%.........:-@@@@@@@                                 
//      %%%%%%%%%%%%%%%%%%%%%%       --#%@@%%%%%%%%%@.........+:#@@@@%                                  
//                                    ::%@%%%%%%%%%@@-........-:-@@                                     
//                                  %%%-:@%%%%%%%%@@@=........:-:@                                      
//                                 %@@@*::%%%%%%%@@@@*........:-:=                                      
//                               @%%@@%%--*%%%%%%@@@@%........:-::                                      
//                             %%%%@@%%%@::#%%%@@@@@@@........::::=                                     
//                                %@%%%%%%::%%%@@@@@@@:.......-::::#                                    
//                               @%%%%%%@%--.+@@@@@@@ -.......=::::- %                                  
//                             @%%%%%%%%%%=--::.%@%   =.......*:::::=====                               
//                            @%%%%%%@@@%%-:--:-      +......- *:::::*+++#% %                           
//                          @%%%%%@@@@@@%@@+=--:*     +......*++*:::++++*#%##                           
//                        %%%%%%%@@@@@@     =-:::*    =.....:@--=-++++=******                           
//                       @%%%%@@             +.:-     =.....+ *=*++++-+++*%%%                           
//                                             -:-:#  -.....#   *++=++++*#%%%@                          
//                                            =::::   .....-     %*+***===%%%@                          
//                                              *--*##.....*     @%*###%=*%%%%@                         
//                                              @=+===....:=+      #%@@%+#%%@%@                         
//                                             @=-=++.....==+*%    @*###%#%@                            
//                                             #=++=#.....*+==+    ####%%#%%@                           
//                                             %..:=:-==+*++==#     %%%%#%%@@                           
//                                             %+=...=.:-::=-%     %%%%##%%%                            
//                                              %:++-...-.**%      *%*##%%                              
//                                               ==+=-=*+-*+       %%%%@@                               
//                                                #+=+=-=@%                                             
//                                                %##%%#%                                               
//                                              %#@#***-@                                               
//                                              #*#%%**#@                                               
//                                               %#+###%@                                               
//                                              *#%@%*#%                                                
//                                             %%%#%#*%%                                                
//                                            @#####%%%%                                                
//                                            #*%##%%%%%                                                
//                                            %#*%%###%                                                 
//                                            #%%###%@                                                  
//                                             %###%@                                                   
#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template<typename T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// #define get find_by_order
// #define find order_of_key
#define ll long long
#define FurinaDeFontaine main
#define gobrr() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define input "input"
#define output "output"
const ll INF = 1e9;
ll mod = 1e9 + 7;
int gcd(int a, int b)
{
    return (b == 0 ? a : gcd(b, a % b));
}
ll lcm(int a, int b)
{
    return 1ll * a * b / gcd(a, b);
}
ll power(ll a, ll b, ll m)
{
    ll res = 1;
    while(b)
    {
        if(b & 1) res = a * res % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
struct SegTree
{
    int n; 
    vector<int> T;
    SegTree (int _n)
    {
        n = 1;
        while(n < _n) n *= 2;
        T.resize(n * 4);
        n *= 2;
    }
    void update(int pos)
    {
        T[pos + n - 1]++;
        for(int j = (pos + n - 1) / 2; j >= 1; j /= 2)
        {
            T[j] = T[j * 2] + T[j * 2 + 1];
        }
    }
    int get(int pos, int l, int r, int ql, int qr)
    {
        if(l > qr || r < ql) return 0;
        if(ql <= l && r <= qr) 
        {
            // cout << l << "pair" << r << " ";
            return T[pos];
        }
        int mid = (l + r) >> 1;
        return get(pos * 2, l, mid, ql, qr) + get(pos * 2 + 1, mid + 1, r, ql, qr);
    }
    int get(int l, int r)
    {
        return get(1, 1, n, l, r);
    }
};
vector<array<int,4> > events;
vector<int> vals;
int n,q;
int FurinaDeFontaine()
{
    if(fopen(input".inp", "r"))
    {
        freopen(input".inp", "r", stdin);
        freopen(output".out", "w", stdout);
    }
    cin >> n >> q;
    events.push_back({-INF, -INF, -INF, -INF});
    vals.push_back(-INF);
    for(int i = 1;i <= n; ++i)
    {
        int u,v; cin >> u >> v;
        int w = u + v;
        events.push_back({u,v,w, i});
        vals.push_back(u);
        vals.push_back(v);
        vals.push_back(w);
    } 
    for(int i = 1;i <= q; ++i)
    {
        int u,v, w; cin >> u >> v >> w;
        events.push_back({u,v,w, -i});
        vals.push_back(u);
        vals.push_back(v);
        vals.push_back(w);
    } 
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    // for(auto x: vals) cout << x << " ";
    // cout << endl;
    for(int i = 1;i <= n + q; ++i) 
    {
        for(int j = 0;j < 3; ++j) events[i][j] = lower_bound(vals.begin(), vals.end(), events[i][j]) - vals.begin();
    }
    sort(events.begin() + 1, events.end());
    reverse(events.begin() + 1, events.end());
    int nums = vals.size();
    SegTree sums(nums + 1);
    SegTree creative(nums + 1);
    // cout << sums.n << endl;
    vector<int> ans(q + 1);
    for(int i = 1;i <= n + q; ++i)
    {
        // for(int j = 0;j < 3; ++j) cout << vals[events[i][j]] << " ";
        // cout << events[i][3] << endl;
        // for(auto x: events[i]) cout << x << " ";
        // cout << endl;
        int j = events[i][3];
        if(j > 0)
        {
            creative.update(events[i][1]);
            sums.update(events[i][2]);
            // for(int i = 1;i <= nums; ++i) cout << i << " " << creative.get(i, nums) << " " << sums.get(i, nums) << endl;
        }
        else
        {
            int k1 = creative.get(events[i][1], nums);
            int k2 = sums.get(events[i][2], nums);
            // for(int i = 1;i <= nums; ++i) cout << i << " " << creative.get(i, nums) << " " << sums.get(i, nums) << endl;
            // cout << k1 << " " << k2 << " " << j << endl;
            ans[-j] = min(k1,k2);
        }
    }
    for(int i = 1;i <= q; ++i) cout << ans[i] << "\n";
    return 0;
}

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

examination.cpp: In function 'int main()':
examination.cpp:185:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |         freopen(input".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:186:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  186 |         freopen(output".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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