oj.uz

Submission #158175

# Submission time Handle Problem Language Result Execution time Memory
158175 2019-10-15T08:36:04 Z mrtsima22 trapezoid (balkan11_trapezoid) C++17
18 / 100
 313 ms 27432 KB 
#pragma GCC optimize "-O3"
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define NumberOfOnes __builtin_popcount
#define LSOne(S) (S & (-S))
#define ll long long
#define two pair<int,int>
#define twoll pair<ll,ll>
#define four pair<two,two>
#define pb push_back
#define eb emplace_back
#define mk make_pair
#define y1 y1922
#define INF 1000000000000000000
#define P 1000000007
#define lmax 1000000000
#define nn 1000003
#define ff first.first
#define fs first.second
#define sf second.first
#define ss second.second
#define f first
#define s second
#define vi vector<int>
#define vll vector<ll>
#define vtwo vector<two>
#define ALL(container) (container).begin(), (container).end()
#define sz(container) (int)(container.size())
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define mid(a,b) (a+b>>1)
#define minN 0
#define maxN 10000000
#define na(x) ((x)<P?(x):(x)-P)
#define ab(a) (-(a)<(a)?(a):-(a))
#define FAST std::ios::sync_with_stdio(false)
#define xRand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rnd rng
#define IT iterator
typedef
tree<
  int,// aq pair<int,int> shegidzlia
  null_type,
  less/*_equal*/<int>,// aqac
  rb_tree_tag,
  tree_order_statistics_node_update>
ordered_set;
// '_equal' mashin ginda roca multiset gchirdeba
template<class key, class value,class cmp = std::less<key>>
using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
ordered_map<int, int> my_map;
inline int rin(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
inline int bin(){
	int x=0;char ch=getchar();
	while (ch<'0'||ch>'9') ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x;
}
const int mod=30013;
int n,a,b,c,d;
vector<pair<two,two> >w;
//			f,s,t,i
two A[200006],dp[2000004];
set<int>s;
set<int>::IT it;
map<int,int>mp;
void upd(int x,two y){
	for(;x<200003;x+=(x&-x)){
			if(y.f>A[x].f){
				A[x]=y;
			}
			else{
				if(y.f==A[x].f){
					A[x].s+=y.s;
					A[x].s%=mod;
				}
			}
		}
}
two qura(int x){
	two ans={1,1};
	for(;x>=1;x-=(x&-x)){
		if(A[x].f+1>ans.f){
			ans={A[x].f+1,max(A[x].s,1)};
		}
		else{
			if(A[x].f+1==ans.f){
				ans.s+=A[x].s;
				ans.s%=mod;
			}
		}
	}
	return ans;
}
int main(){FAST;xRand;
cin>>n;
for(int i=0;i<n;i++){
	cin>>a>>b>>c>>d;
	w.pb({{a,c},{i,-1}});
	w.pb({{b,d},{i,-1}});
	s.insert(c);
	s.insert(d);
}
c=0;
for(it=s.begin();it!=s.end();it++){
	mp[(*it)]=++c;
}
for(int i=0;i<2*n;i++){
	w[i].fs=mp[w[i].fs];
}
w.pb({{lmax,n+2},{n,-1}});
w.pb({{lmax+1,n+3},{n+1,-1}});
for(int i=0;i<sz(w);i++){
		w[i].ss=!(i&1);
}
sort(ALL(w));
for(int i=0;i<sz(w);i++){
	if(w[i].ss==1){
		dp[w[i].sf]=qura(w[i].fs);
	}else{
		upd(w[i].fs,dp[w[i].sf]);
	}
}
cout<<dp[n-1].f<<" "<<dp[n-1].s<<endl;
}
/*

                   *         *
                  * *       * *
                 *   *     *   *
                *     *   *     *
                 *   *   * *   *
                  *   *   *   *
                   *   * *   *
                     *  *   *
					   *  *


*/

Compilation message

trapezoid.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")

Subtask #1
18.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 376 KB Partially correct
2 Partially correct 2 ms 376 KB Partially correct
3 Partially correct 3 ms 504 KB Partially correct
4 Partially correct 4 ms 632 KB Partially correct
5 Partially correct 6 ms 888 KB Partially correct
6 Incorrect 7 ms 1244 KB Output isn't correct
7 Partially correct 10 ms 1528 KB Partially correct
8 Incorrect 12 ms 1780 KB Output isn't correct
9 Partially correct 26 ms 3200 KB Partially correct
10 Partially correct 54 ms 5744 KB Partially correct
11 Incorrect 64 ms 7148 KB Output isn't correct
12 Incorrect 163 ms 13924 KB Output isn't correct
13 Incorrect 173 ms 16528 KB Output isn't correct
14 Incorrect 189 ms 19356 KB Output isn't correct
15 Incorrect 255 ms 20688 KB Output isn't correct
16 Incorrect 258 ms 21932 KB Output isn't correct
17 Incorrect 260 ms 23388 KB Output isn't correct
18 Partially correct 283 ms 24540 KB Partially correct
19 Incorrect 273 ms 25884 KB Output isn't correct
20 Incorrect 313 ms 27432 KB Output isn't correct