Предел памяти превысил сегментное дерево в плакатах SPOJ?

Question

Для горизонтальной части стены и N слоев красок, нанесенных с координатами Xi на Yi, выведите на экран отчетливое количество слоев.

Вот ссылка проблемы http://www.spoj.com/problems/POSTERS/

Вот мое решение http://ideone.com/gBJKnL

подход: Я попытался решить эту проблему путем ленива обновления значений дочерних узлов через сегмент дерево, последнее значение заменяет старшее в их ленивых обновлениях. Таким образом, в горизонтальное поперечное сечение применяется только недавняя краска. хотя код отлично работает в пользовательских тестовых случаях, он занимает много памяти и прерывается онлайн-судьей.

#include <iostream> 
#include <set> 
#include <vector> 
#define MAX 10000000+100 
typedef long long int ll; 
using namespace std; 
ll Tree[3*MAX],lazy[MAX*2]; 


void Update(ll s,ll start,ll end,ll left,ll right,ll value) 
{ 
    if(lazy[s]!=0) 
    { 
     Tree[s]=(lazy[s]*(end-start+1)); 
     if(start!=end)lazy[2*s+1]=lazy[s],lazy[s*2+2]=lazy[s]; 
     lazy[s]=0; 
    } 
    if(start>end||left>end||right<start)return; 
    if(start>=left&&end<=right) 
    { 
     Tree[s] = (value*(end-start+1)); 
     if(start!=end) 
     { 
      lazy[2*s+1]=value; 
      lazy[2*s+2]=value; 
     } 
     return ; 
    } 
    ll mid=(start+end)/2; 
    Update(2*s+1,start,mid,left,right,value); 
    Update(2*s+2,mid+1,end,left,right,value); 
    Tree[s] = Tree[s*2+1]+Tree[2*s+2]; 
} 

ll Read(ll s,ll start,ll end,ll left,ll right) 
{ 
    if(start>end||start>right||end<left)return 0; 
    if(lazy[s]!=0) 
    { 
     Tree[s]=(lazy[s]*(end-start+1)); 
     if(start!=end) 
     { 
      lazy[2*s+1]=lazy[s]; 
      lazy[2*s+2]=lazy[s]; 
     } 
     lazy[s]=0; 
    } 
    if(start>=left&&end<=right)return Tree[s]; 
    else return (Read(2*s+1,start,(start+end)/2,left,right)+Read(2*s+2,1+((start+end)/2),end,left,right)); 

} 
int main() { 
    // your code goes here 
    ll t; 
    cin>>t; 
    while(t--) 
    { 
     ll n,z=1,li=-1; 
     cin>>n; 
     vector<pair<ll,ll> > b; 
     for(ll i=0;i<n;i++) 
     { 
      ll u,v; 
      li = max(li,v); 
      cin>>u>>v; 
      b.push_back(make_pair(u-1,v-1)); 
     } 
     for(auto v: b) 
      Update(0,0,li+2,v.first,v.second,z++); 
     set<ll> a; 

     for(ll i=0;i<li+2;i++)cout<<Read(0,0,li+2,i,i)<<" ",a.insert(Read(0,0,li+2,i,i)); 
     cout<<endl; 
     cout<<a.size()-1<<endl; 
    } 
    return 0; 
} 

Answer 1

Вот как вы должны делать это:

#include <bits/stdc++.h> 
#define mx 400005 
using namespace std; 

int tr[mx], lz[mx]; 
int t, n, l, r; 

void update(int node, int s, int e, int l, int r, int val) 
{ 
    if(lz[node]!=0) 
    { 
     tr[node]=lz[node]; 
     if(s!=e) 
     { 
      lz[node*2]=lz[node]; 
      lz[node*2+1]=lz[node]; 
     } 
     lz[node]=0; 
    } 
    if(s>e || r<s || l>e) 
     return; 
    if(s>=l && e<=r) 
    { 
     tr[node]=val; 
     if(s!=e) 
     { 
      lz[2*node]=val; 
      lz[2*node+1]=val; 
     } 
     return; 
    } 
    int m=s+(e-s)/2; 
    update(2*node,s,m,l,r,val); 
    update(2*node+1,m+1,e,l,r,val); 
    tr[node]=val; 
    //tr[node]=max(tr[2*node],tr[2*node+1]); 
} 

int query(int node, int s, int e, int l, int r) 
{ 
    if(r<s || e<l) 
     return 0; 
    if(lz[node]!=0) 
    { 
     tr[node]=lz[node]; 
     if(s!=e) 
     { 
      lz[node*2]=lz[node]; 
      lz[node*2+1]=lz[node]; 
     } 
     lz[node]=0; 
    } 
    if(l<=s && r>=e) 
     return tr[node]; 
    int m=s+(e-s)/2; 
    return query(2*node,s,m,l,r)+query(2*node+1,m+1,e,l,r); 
} 

int main() 
{ 
    //cout << "Hello world!" << endl; 
    cin>>t; 
    while(t--) 
    { 
     for(int i=0; i<mx; i++) tr[i]=0; 

     cin>>n; 

     int lr[n+1][2]; 

     map<int,bool> mark; 
     vector<int> vec; 
     //int c=0; 
     for(int i=0; i<n; i++) 
     { 
      cin>>l>>r; 
      lr[i][0]=l; 
      lr[i][1]=r; 
      if(mark[l]==0) 
      { 
       vec.push_back(l); 
       mark[l]=1; 
      } 
      if(mark[r]==0) 
      { 
       vec.push_back(r); 
       mark[r]=1; 
      } 
     } 

     sort(vec.begin(), vec.end()); 
     map<int,int> mp; 
     int c=1; 
     for(int i=0; i<vec.size(); i++) 
      mp[vec[i]]=c++; 

     for(int i=0; i<n; i++) 
     { 
      //cout<<mp[lr[i][0]]<<" "<<mp[lr[i][1]]<<"\n"; 
      update(1,1,vec.size(),mp[lr[i][0]],mp[lr[i][1]],i+1); 
     } 

     set<int> ans; 
     for(int i=1; i<=vec.size(); i++) 
     { 
      //cout<<query(1,1,vec.size(),i,i)<<" "; 
      ans.insert(query(1,1,vec.size(),i,i)); 
     } 
     int k = ans.size(); 
     if(ans.find(0) != ans.end()) 
      k--; 
     printf("%d\n",k); 
    } 
    return 0; 
}