Submission #1272378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272378		sasde	Examination (JOI19_examination)	C++20	100 / 100	851 ms	78808 KiB

examination

#include<bits/stdc++.h>
using namespace std;
bool M1;
#define PI 3.14159265358979323846
#define sz(a) (int)a.size()
#define all(x) x.begin(),x.end()
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii,ii>
#define se second
#define fi first
#define ffi fi.fi
#define sfi se.fi
#define sse se.se
#define fse fi.se
#define lt(i, c, d) for(int i = c; i <= d; ++i)
#define fl(i, c, d) for(int i = d; i >= c; --i)
#define pb push_back
#define emb emplace_back
#define emf emplace_front
#define em emplace
#define look_memory cerr<<abs(&M2-&M1)/1024.0/1024<<'\n'
#define look_time   cerr << "TIME : " << clock() * 0.001 << "s" <<'\n'
const int N=1e5+5,lg=30,mod=1e9+7;
int node,query,ans[N];
ii a[N];
struct pt
{
  int a,b,c,i;
}b[N];
struct BIT2D{
  int n;
  vector<vector<int>>bit,node;
  BIT2D(){};
  BIT2D(int _n):n(_n),bit(n+5),node(n+5){};
  void fakeupdate(int u,int v){
    for(;u<=n;u+=u&-u){
      node[u].pb(v);
    }
  }
  void fakeget(int u,int v){
    for(;u>0;u-=u&-u){
      node[u].pb(v);
    
    }
  }
  void fakequery(int x, int y, int u, int v){
    fakeget(u,v);
    fakeget(x-1,v);
    fakeget(u,y-1);
    fakeget(x-1,y-1);
  }
  void fakeupdaterange(int x, int y, int u, int v){
    fakeupdate(u+1,v+1);
    fakeupdate(x,v+1);
    fakeupdate(u+1,y);
    fakeupdate(x,y);
  }
  void start(){
    for(int i=1;i<=n;++i){
    sort(all(node[i]));
    node[i].erase(unique(all(node[i])),node[i].end());
    bit[i].assign(node[i].size()+5,0);
    }
  }
  void update(int u,int v,int val){
      while(u<=n){
         for(int i=lower_bound(all(node[u]),v)-node[u].begin()+1;i<=node[u].size();i+=i&(-i))
          bit[u][i-1]+=val;
         // cout <<u<<" "<<v<<" "<<lower_bound(all(node[u]),v)-node[u].begin()+1<<" "<<node[u].size()<<" "<<bit[u].size()<<'\n';;
         u+=u&(-u);
      }
  }
  int get(int u,int v){
    int res=0;
      while(u>0){
        for(int i=lower_bound(all(node[u]),v)-node[u].begin()+1;i>0;i-=i&(-i))
          res+=bit[u][i-1];
         u-=u&(-u);
      }

    return res;
  }
  void updaterange(int x,int y,int u,int v,int val){
    update(u+1,v+1,val);
    update(x,v+1,-val);
    update(u+1,y,-val);
    update(x,y,val);
  }
  int query(int x, int y, int u, int v){
       return get(u, v) - get(x-1, v) - get(u,y-1) + get(x-1,y-1);
  }
} tree;
vector<int>nen;
int ne(int u){
  return lower_bound(all(nen),u)-nen.begin()+1;
}
bool M2;
void solve(){
  cin >> node >> query;
  for(int i=1;i<=node;++i){
    cin >> a[i].fi >> a[i].se;
    nen.emb(a[i].se);
    nen.emb(a[i].fi+a[i].se);
  }
  // tree =BIT2D(node);
  sort(a+1,a+1+node,greater<ii>());
  for(int i=1;i<=query;++i){
     cin >> b[i].a >> b[i].b >> b[i].c;
     b[i].i=i;
     nen.emb(b[i].b);
     nen.emb(b[i].c);
  }
  sort(b+1,b+1+query,[&](const pt &x,const pt &y){
    return x.a>y.a;
  });
  sort(all(nen));
  nen.erase(unique(all(nen)),nen.end());
  int n=sz(nen);
  tree =BIT2D(n);
  for(int i=1;i<=node;++i){
    int u=ne(a[i].se);
    int v=ne(a[i].se+a[i].fi);
    tree.fakeupdate(u,v);
  }
  for(int i=1;i<=query;++i){
    int u=ne(b[i].b);
    int v=ne(b[i].c);
    tree.fakequery(u,v,n,n);
  }
  tree.start();
  for(int i=1,j=1;i<=query;++i){
      while(j<=node&&b[i].a<=a[j].fi){
            int u=ne(a[j].se);
            int v=ne(a[j].se+a[j].fi);
            tree.update(u,v,1);
        ++j;
      }
    int u=ne(b[i].b);
    int v=ne(b[i].c);
    ans[b[i].i]=tree.query(u,v,n,n);
  }
  for(int i=1;i<=query;++i)cout << ans[i]<<'\n';

}
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    #define task "aws"
    if(fopen(task".inp","r")){
      freopen(task".inp","r",stdin);
      freopen(task".out","w",stdout);
    }
    int t=1;
 //   cin >> t;
while(t--){
    solve();cout<<'\n';
}
look_memory;
look_time;
}

Compilation message (stderr)

examination.cpp:146:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  146 | main()
      | ^~~~
examination.cpp: In function 'int main()':
examination.cpp:153:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |       freopen(task".inp","r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
examination.cpp:154:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |       freopen(task".out","w",stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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