Submission #862434

#	Time	Username	Problem	Language	Result	Execution time	Memory
862434		HossamHero7	Osumnjičeni (COCI21_osumnjiceni)	C++14	0 / 110	190 ms	12936 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
void compress(vector<int> &a){
    int n = a.size();
    vector<pair<int,int>> b(n);
    for(int i=0;i<n;i++){
        b[i].first = a[i];
        b[i].second = i;
    }
    sort(b.begin(),b.end());
    a[b[0].second] = 1;
    int cnt = 1;
    for(int i=1;i<n;i++){
        if(b[i].first == b[i-1].first){
            a[b[i].second] = a[b[i-1].second];
        }
        else a[b[i].second] = ++cnt;
    }
}
struct segTree{
    int n;
    vector<int> tree;
    vector<pair<int,int>> lazy;
    segTree(int _n){
        n = _n;
        tree.resize(4*n+5);
        lazy.resize(4*n+5);
    }
    void prop(int node,int l,int r){
        if(lazy[node].second) tree[node] = 0;
        tree[node] += (r - l + 1) * lazy[node].first;
        if(l != r){
            lazy[node<<1].first += lazy[node].first;
            lazy[node<<1|1].first += lazy[node].first;
            lazy[node<<1].second |= lazy[node].second;
            lazy[node<<1|1].second |= lazy[node].second;
        }
        lazy[node] = {0,0};
    }
    void update(int node,int l,int r,int lQ,int rQ,int val){
        if(l>r) return;
        if(lazy[node].first || lazy[node].second) prop(node,l,r);
        if(lQ>r || l>rQ) return;
        if(lQ<=l&&r<=rQ) return lazy[node].first += val, prop(node,l,r), void();
        int md = l + r >> 1;
        update(node<<1,l,md,lQ,rQ,val), update(node<<1|1,md+1,r,lQ,rQ,val);
        tree[node] = tree[node<<1] + tree[node<<1|1];   
    }
    void clear(){
        if(lazy[1].first || lazy[1].second) prop(1,1,n);
        lazy[1] = {0,1}, prop(1,1,n);
    }
    void update(int l,int r,int val=1){
        update(1,1,n,l,r,val);
    }
    int query(int node,int l,int r,int lQ,int rQ){
        if(l>r) return 0;
        if(lazy[node].first || lazy[node].second) prop(node,l,r);
        if(lQ>r || l>rQ) return 0;
        if(lQ<=l&&r<=rQ) return tree[node];
        int md = l + r >> 1;
        return query(node<<1,l,md,lQ,rQ) + query(node<<1|1,md+1,r,lQ,rQ);
    }
    int query(int l,int r){
        return query(1,1,n,l,r);
    }
};
void solve(){
    int n;
    cin>>n;
    vector<pair<int,int>> v(n);
    for(auto &[l,r] : v) cin>>l>>r;
    vector<int> tmp;
    for(auto [l,r] : v) tmp.push_back(l);
    for(auto [l,r] : v) tmp.push_back(r);
    compress(tmp);
    for(int i=0;i<n;i++) v[i] = {tmp[i],tmp[i+n]};
    segTree sg(n);
    int ans = 1;
    for(auto [l,r] : v){
        if(sg.query(l,r)) {
            sg.clear();
            ans ++;
        }
        sg.update(l,r);
    }
    cout<<ans<<endl;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'void segTree::update(int, int, int, int, int, int)':
Main.cpp:47:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |         int md = l + r >> 1;
      |                  ~~^~~
Main.cpp: In member function 'int segTree::query(int, int, int, int, int)':
Main.cpp:63:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |         int md = l + r >> 1;
      |                  ~~^~~
Main.cpp: In function 'void solve()':
Main.cpp:74:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |     for(auto &[l,r] : v) cin>>l>>r;
      |               ^
Main.cpp:76:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   76 |     for(auto [l,r] : v) tmp.push_back(l);
      |              ^
Main.cpp:77:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |     for(auto [l,r] : v) tmp.push_back(r);
      |              ^
Main.cpp:82:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |     for(auto [l,r] : v){
      |              ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 50