답안 #166123

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
166123 2019-11-30T20:15:26 Z theStaticMind Garaža (COCI17_garaza) C++14
120 / 160
4000 ms 178380 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;
vector<int>arr;
map<int,int>F[100005];
bool comp(ii& a,ii& b){
      return a.first>b.first||(a.first==b.first&&a.second>b.second);
}
struct node{
      long long int cnt;
      int size;
      map<int,int>pre,suff;
      node(int s){
            cnt=0;
            size=s;
      }
      void merge(node& L,node& R){
            size=L.size+R.size;
            if(L.size==0){
                  cnt=R.cnt;
                  pre=R.pre;
                  suff=R.suff;
                  return;
            }
            if(R.size==0){
                  cnt=L.cnt;
                  pre=L.pre;
                  suff=L.suff;
                  return;
            }
            pre.clear();
            suff.clear();
            vector<ii>ind;
            ind.pb({0,0});
            for(map<int,int>::iterator itr=L.suff.begin();itr!=L.suff.end();itr++){
                  ind.pb({itr->second,R.pre[itr->first]});
            }
            sort(all(ind),comp);
            int w=ind[0].second;
            for(int i=1;i<ind.size();i++){
                  cnt+=(long long int)((long long int)ind[i-1].first-(long long int)ind[i].first)*(long long int)w;
                  w=max(w,ind[i].second);
            }
            cnt+=L.cnt+R.cnt;
            pre=L.pre;
            for(map<int,int>::iterator itr=L.pre.begin();itr!=L.pre.end();itr++){
                  if(itr->second==L.size)pre[itr->first]=itr->second+R.pre[itr->first];
            }
            suff=R.suff;
            for(map<int,int>::iterator itr=R.suff.begin();itr!=R.suff.end();itr++){
                  if(itr->second==R.size)suff[itr->first]=itr->second+L.suff[itr->first];
            }
      }
      void _merge(node& L,node& R){
            size=L.size+R.size;
            if(L.size==0){
                  swap(cnt,R.cnt);
                  swap(pre,R.pre);
                  swap(suff,R.suff);
                  return;
            }
            if(R.size==0){
                  swap(cnt,L.cnt);
                  swap(pre,L.pre);
                  swap(suff,L.suff);
                  return;
            }
            pre.clear();
            suff.clear();
            vector<ii>ind;
            ind.pb({0,0});
            for(map<int,int>::iterator itr=L.suff.begin();itr!=L.suff.end();itr++){
                  ind.pb({itr->second,R.pre[itr->first]});
            }
            sort(all(ind),comp);
            int w=ind[0].second;
            for(int i=1;i<ind.size();i++){
                  cnt+=(long long int)((long long int)ind[i-1].first-(long long int)ind[i].first)*(long long int)w;
                  w=max(w,ind[i].second);
            }
            cnt+=L.cnt+R.cnt;
            swap(pre,L.pre);
            for(map<int,int>::iterator itr=pre.begin();itr!=pre.end();itr++){
                  if(itr->second==L.size)itr->second+=R.pre[itr->first];
            }
            swap(suff,R.suff);
            for(map<int,int>::iterator itr=suff.begin();itr!=suff.end();itr++){
                  if(itr->second==R.size)itr->second+=L.suff[itr->first];
            }
      }
};
vector<node>seg;
int S;
void build(){
      S=(1<<(int)ceil(log2(seg.size())));
      int l=S-seg.size();
      for(int i=0;i<l;i++)seg.pb(node(0));
      reverse(all(seg));
      for(int i=1;i<seg.size();i+=2){
            node temp(0);
            temp.merge(seg[i],seg[i-1]);
            seg.pb(temp);
      }
      seg.pb(node(0));
      reverse(all(seg));
}
vector<node>t;
int ind=0;
void query(int j,int a,int b,int x,int y){
      if(y<a||b<x)return;
      if(a<=x&&y<=b){
            t[2]=seg[j];
            t[ind^1]=node(0);
            t[ind^1]._merge(t[ind],t[2]);
            ind^=1;
      }
      else{
            query(j*2,a,b,x,(x+y)/2);query(j*2+1,a,b,(x+y)/2+1,y);
      }
}
void update(int j){
      while(j>0){
            seg[j]=node(0);
            seg[j].merge(seg[j*2],seg[j*2+1]);
            j/=2;
      }
}
int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
      int n,q;
      cin>>n>>q;
      seg.resize(n,node(1));
      for(int i=0;i<n;i++){
            int x;
            cin>>x;
            arr.pb(x);
            for(int j=2;j*j<=x;j++){
                  if(x%j==0){
                        F[i][j]=1;
                        while(x%j==0)x/=j;
                  }
            }
            if(x>1)F[i][x]=1;
            seg[i].pre=F[i];
            seg[i].suff=F[i];
            if(F[i].empty())seg[i].cnt=0;
            else seg[i].cnt=1;
      }
      build();
      t.resize(3,node(0));
      while(q--){
            int k,x,y;
            cin>>k>>x>>y;
            if(k==1){
                  x--;
                  F[x].clear();
                  for(int j=2;j*j<=y;j++){
                        if(y%j==0){
                              F[x][j]=1;
                              while(y%j==0)y/=j;
                        }
                  }
                  if(y>1)F[x][y]=1;
                  int i=seg.size()-S+x;
                  seg[i].pre=F[x];
                  seg[i].suff=F[x];
                  if(F[x].empty())seg[i].cnt=0;
                  else seg[i].cnt=1;
                  update(i/2);
            }
            else{
                  x--,y--;
                  query(1,x,y,0,S-1);
                  cout<<t[ind].cnt<<"\n";
                  t[0]=node(0);
                  t[1]=node(0);
            }
      }
}

Compilation message

garaza.cpp: In member function 'void node::merge(node&, node&)':
garaza.cpp:47:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=1;i<ind.size();i++){
                         ~^~~~~~~~~~~
garaza.cpp: In member function 'void node::_merge(node&, node&)':
garaza.cpp:84:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=1;i<ind.size();i++){
                         ~^~~~~~~~~~~
garaza.cpp: In function 'void build()':
garaza.cpp:106:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=1;i<seg.size();i+=2){
                   ~^~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 6428 KB Output is correct
2 Correct 36 ms 7832 KB Output is correct
3 Correct 145 ms 13580 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 696 ms 41804 KB Output is correct
2 Correct 427 ms 34224 KB Output is correct
3 Correct 1481 ms 45340 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 962 ms 49204 KB Output is correct
2 Correct 2015 ms 85016 KB Output is correct
3 Correct 3163 ms 85576 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1672 ms 93340 KB Output is correct
2 Correct 3790 ms 178380 KB Output is correct
3 Execution timed out 4081 ms 139728 KB Time limit exceeded