?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
158542039 |
Practice: divakar.dc3 |
1679C - 26 | C++17 (GCC 7-32) | Time limit exceeded on test 3 | 1000 ms | 4692 KB | 2022-05-26 18:07:25 | 2022-05-26 18:07:25 |
#include<bits/stdc++.h> #define ll long long #define lld long double #define pb push_back #define fr(a,b) for(int i = a; i < b; i++) #define rep(i,a,b) for(int i = a; i < b; i++) #define mod 1000000007 #define mod1 998244353 #define inf (1LL<<60) #define all(x) (x).begin(), (x).end() #define prDouble(x) cout << fixed << setprecision(10) << x #define triplet pair<ll,pair<ll,ll>> #define goog(tno) cout << "Case #" << tno <<": " #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL) #define read(x) int x; cin >> x using namespace std; void init_code(){ fast_io; #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif } ll fast_power(ll base,ll power,ll MOD) { if(power==0) return 1; if(power==1) return base%MOD; ll result=fast_power(base,power/2,MOD)%MOD; if(power%2==0) return ((result%MOD)*(result%MOD))%MOD; ll a=((result%MOD)*(base%MOD))%MOD; a=((a%MOD)*(result%MOD))%MOD; return a%MOD; } ll query(ll s,ll e,ll left,ll right,ll treeNode,ll *tree,ll *arr){ if(left>e||right<s){ return 0; } if(left<=s&&e<=right){ return tree[treeNode]; } int mid=(s+e)/2; ll ans1=query(s,mid,left,right,2*treeNode,tree,arr); ll ans2=query(mid+1,e,left,right,2*treeNode+1,tree,arr); return ans1+ans2; } void insert(ll s,ll e,ll idx,ll treeNode,ll *tree,ll *arr){ if(s==e){ if(s==idx){ arr[idx]++; // tree[treeNode]=1; } if(arr[s]>0) tree[treeNode]=1; else tree[treeNode]=0; return; } ll mid=(s+e)/2; insert(s,mid,idx,2*treeNode,tree,arr); insert(mid+1,e,idx,2*treeNode+1,tree,arr); tree[treeNode]=tree[2*treeNode]+tree[2*treeNode+1]; } void remove(ll s,ll e,ll idx,ll treeNode,ll *tree,ll *arr){ if(s==e){ if(s==idx){ arr[idx]--; // tree[treeNode]=0; } if(arr[s]>0) tree[treeNode]=1; else tree[treeNode]=0; return ; } ll mid=(s+e)/2; remove(s,mid,idx,2*treeNode,tree,arr); remove(mid+1,e,idx,2*treeNode+1,tree,arr); tree[treeNode]=tree[2*treeNode]+tree[2*treeNode+1]; } int main(){ init_code(); ll n,q; cin>>n>>q; ll row[n]={0}; ll col[n]={0}; ll tree1[2*n]={0}; ll tree2[2*n]={0}; while(q--){ // cout<<q<<endl; ll t; cin>>t; if(t==1||t==2){ ll x,y; cin>>x>>y; if(t==1){ insert(0,n-1,x-1,1,tree1,row); insert(0,n-1,y-1,1,tree2,col); } else{ // tree[x-1]=0; // tree[y-1]=0; remove(0,n-1,x-1,1,tree1,row); remove(0,n-1,y-1,1,tree2,col); } } else{ ll x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2; // scanf("%lld %lld %lld %lld",&x1,&y1,&x2,&y2); ll ans1=query(0,n-1,x1-1,x2-1,1,tree1,row); ll ans2=query(0,n-1,y1-1,y2-1,1,tree2,col); // cout<<ans1<<" "<<ans2<<endl; if(ans1==abs(x2-x1+1)||ans2==(y2-y1+1)){ cout<<"Yes\n"; } else{ cout<<"No\n"; } } } // for(ll i=0;i<n;i++){ // cout<<arr[i]<<" "; // } // cout<<endl; // for(ll i=0;i<4*n;i++){ // cout<<tree[i]<<" "; // } // cout<<endl; }
?
?
?
?