oj.uz

답안 #168465

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
168465 2019-12-13T08:15:51 Z theStaticMind Poklon (COCI17_poklon) C++14
140 / 140
 1597 ms 96308 KB 
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
//#define int long long int
using namespace std;
struct Fenwick{
      vector<int>bit;
      int size;

      void modify(int j,int v){
            for(;j<size;j+=j&-j)bit[j]+=v;
      }

      int query(int j){
            int v=0;
            for(;j>0;j-=j&-j)v+=bit[j];
            return v;
      }

      Fenwick(int n){
            bit=vector<int>(n,0);
            size=n;
      }
};
vector<pair<ii,int>>off[500005];
int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
   //   freopen("q.gir","r",stdin);
   //   freopen("q.cik","w",stdout);
      int n,q;
      cin>>n>>q;
      vector<int>arr(n+1);
      vector<pair<ii,int>>Q;
      vector<int>ans(q);
      map<int,map<int,int>>L,R;
      for(int i=1;i<=n;i++){
            cin>>arr[i];
            L[arr[i]][i]=0;
            R[arr[i]][i]=n+1;
      }
      for(int i=0;i<q;i++){
            int x,y;
            cin>>x>>y;
            Q.pb({{x,y},i});
      }
      sort(all(Q));
      for(map<int,map<int,int>>::iterator it=L.begin();it!=L.end();it++){
            for(map<int,int>::iterator itr=++it->second.begin();itr!=it->second.end();itr++){
                  itr->second=prev(itr)->first;
            }
      }
      for(map<int,map<int,int>>::iterator it=R.begin();it!=R.end();it++){
            for(map<int,int>::iterator itr=--it->second.end();itr!=it->second.begin();itr--){
                  prev(itr)->second=itr->first;
            }
      }
      for(map<int,map<int,int>>::iterator it=L.begin();it!=L.end();it++){
            int x=it->first;
            for(map<int,int>::iterator itr=it->second.begin();itr!=it->second.end();itr++){
                  int ind=itr->first;
                  int l=itr->second;
                  int r=R[x][ind];
                  if(r==n+1)continue;
                  int rr=R[x][r];
                  off[l+1].pb({{r,rr},1});
                  off[ind+1].pb({{r,rr},-1});
            }
      }
      Fenwick data(500005);
      int ind=0;
      for(int i=0;i<=n;i++){
            for(int j=0;j<off[i].size();j++){
                  data.modify(off[i][j].first.first,off[i][j].second);
                  data.modify(off[i][j].first.second,-off[i][j].second);
            }
            while(ind<q&&Q[ind].first.first==i){
                  ans[Q[ind].second]=data.query(Q[ind].first.second);
                  ind++;
            }
      }
      for(int i=0;i<q;i++)cout<<ans[i]<<"\n";
}

Compilation message

poklon.cpp: In function 'int32_t main()':
poklon.cpp:78:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<off[i].size();j++){
                         ~^~~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 14072 KB Output is correct
2 Correct 15 ms 14072 KB Output is correct
3 Correct 16 ms 14200 KB Output is correct
4 Correct 26 ms 14812 KB Output is correct
5 Correct 240 ms 30240 KB Output is correct
6 Correct 254 ms 30268 KB Output is correct
7 Correct 578 ms 47012 KB Output is correct
8 Correct 939 ms 63468 KB Output is correct
9 Correct 1240 ms 79808 KB Output is correct
10 Correct 1597 ms 96308 KB Output is correct