Submission #212762

#	Time	Username	Problem	Language	Result	Execution time	Memory
212762		tatyam	Sails (IOI07_sails)	C++17	100 / 100	637 ms	3960 KiB

sails

#include <bits/stdc++.h>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;
using pii = pair<int, int>;
using ll = long long;
#define rep(a) for(int i = 0; i < a; i++)
#define each(i,a) for(auto&& i : a)
#define all(a) begin(a), end(a)


struct P{
    int cnt, sum;
};
int main(){
    int n;
    cin >> n;
    vector<pii> a(n);
    each(i, a) cin >> i.first >> i.second;
    sort(all(a));
    rope<P> dp;
    int siz = a[0].first;
    dp.push_back({siz, siz});
    each(i, a){
        if((*dp.rbegin()).cnt) dp.push_back({0, 0});
        if(siz < i.first){
            P a = dp[0];
            a.cnt += i.first - siz;
            siz = i.first;
            a.sum = siz;
            dp.replace(0, a);
        }
        int at = partition_point(dp.begin(), dp.end(), [&](const P& a){ return siz - a.sum < i.second; }) - dp.begin() - 1;
        int cnt = i.second - siz + dp[at].sum;
        P a = dp[at + 1];
        a.cnt += cnt;
        a.sum += cnt;
        dp.replace(at + 1, a);
        cnt = dp[at].cnt - cnt;
        dp.erase(dp.mutable_begin() + at);
        dp.push_front({0, siz});
        a = dp[at];
        a.cnt += cnt;
        dp.replace(at, a);
    }
    ll ans = 0;
    rep(dp.size()) ans += ll(dp[i].cnt) * (i - 1) * i / 2;
    cout << ans << endl;
}

Compilation message (stderr)

sails.cpp: In function 'int main()':
sails.cpp:7:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(a) for(int i = 0; i < a; i++)
                               ~~^~~~~~~~~~
 #define each(i,a) for(auto&& i : a)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 #define all(a) begin(a), end(a)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
 
 ~                                
 
 ~                                
 struct P{
 ~~~~~~~~~~                       
     int cnt, sum;
     ~~~~~~~~~~~~~~               
 };
 ~~~                              
 int main(){
 ~~~~~~~~~~~~                     
     int n;
     ~~~~~~~                      
     cin >> n;
     ~~~~~~~~~~                   
     vector<pii> a(n);
     ~~~~~~~~~~~~~~~~~~           
     each(i, a) cin >> i.first >> i.second;
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     sort(all(a));
     ~~~~~~~~~~~~~~               
     rope<P> dp;
     ~~~~~~~~~~~~                 
     int siz = a[0].first;
     ~~~~~~~~~~~~~~~~~~~~~~       
     dp.push_back({siz, siz});
     ~~~~~~~~~~~~~~~~~~~~~~~~~~   
     each(i, a){
     ~~~~~~~~~~~~                 
         if((*dp.rbegin()).cnt) dp.push_back({0, 0});
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
         if(siz < i.first){
         ~~~~~~~~~~~~~~~~~~~      
             P a = dp[0];
             ~~~~~~~~~~~~~        
             a.cnt += i.first - siz;
             ~~~~~~~~~~~~~~~~~~~~~~~~
             siz = i.first;
             ~~~~~~~~~~~~~~~      
             a.sum = siz;
             ~~~~~~~~~~~~~        
             dp.replace(0, a);
             ~~~~~~~~~~~~~~~~~~   
         }
         ~~                       
         int at = partition_point(dp.begin(), dp.end(), [&](const P& a){ return siz - a.sum < i.second; }) - dp.begin() - 1;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
         int cnt = i.second - siz + dp[at].sum;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
         P a = dp[at + 1];
         ~~~~~~~~~~~~~~~~~~       
         a.cnt += cnt;
         ~~~~~~~~~~~~~~           
         a.sum += cnt;
         ~~~~~~~~~~~~~~           
         dp.replace(at + 1, a);
         ~~~~~~~~~~~~~~~~~~~~~~~  
         cnt = dp[at].cnt - cnt;
         ~~~~~~~~~~~~~~~~~~~~~~~~ 
         dp.erase(dp.mutable_begin() + at);
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
         dp.push_front({0, siz});
         ~~~~~~~~~~~~~~~~~~~~~~~~~
         a = dp[at];
         ~~~~~~~~~~~~             
         a.cnt += cnt;
         ~~~~~~~~~~~~~~           
         dp.replace(at, a);
         ~~~~~~~~~~~~~~~~~~~      
     }
     ~~                           
     ll ans = 0;
     ~~~~~~~~~~~~                 
     rep(dp.size()) ans += ll(dp[i].cnt) * (i - 1) * i / 2;
     ~~~~~~~~~~~~~                
sails.cpp:47:5: note: in expansion of macro 'rep'
     rep(dp.size()) ans += ll(dp[i].cnt) * (i - 1) * i / 2;
     ^~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10