Mendo Judge Discussion Board - Forums
Search
Recent Topics
Hottest Topics
Member Listing
Back to home page
Фотографија
Forum Index
»
Задачи од национални натпревари
Author
Message
04/04/2013 18:19:21
Subject:
Фотографија
polincevn
Joined: 14/02/2012 15:07:37
Messages: 9
Offline
Ми паѓа само на еден пример (7миот, ако е важно). Мислења?
#include<cctype> #include<cmath> #include<string> #include<list> #include<deque> #include<stack> #include<utility> #include<sstream> #include<bitset> #include<vector> #include<algorithm> #include<cstring> #include<map> #include<set> #include<queue> #include<set> #include<iostream> #include<stdio.h> #include<climits> using namespace std; #define pb push_back #define mp make_pair #define ms(a,i) memset(a,i,sizeof(a)) #define all(c) (c).begin(), (c).end() #define sz size() typedef long long LL; typedef pair<int,int> PII; typedef vector<int> VI; typedef vector<pair><int , int> > VPII; typedef vector<string> VS; int tree[100010],n; VI vlez,sorted; int query(int x) { int sum=0; for (int i=x;i>0;i-=(i & -i)) sum+=tree[i]; return sum; } void update(int x , int val) { for (int i=x;i<=n;i+=(i & -i)) tree[i]+=val; return; } int main() { cin>>n; for (int i=0;i<n;i++) { int mom; cin>>mom; vlez.pb(mom); } sorted=vlez; sort(all(sorted)); ms(tree,0); for (int i=0;i<n;i++) vlez[i]=lower_bound(all(sorted),vlez[i])-sorted.begin(); int ans1[100010] , ans2[100010]; for (int i=0;i<n;i++) { vlez[i]++; update(vlez[i],1); ans1[i]=query(n)-query(vlez[i]); } ms(tree,0); for (int i=n-1;i>=0;i--) { update(vlez[i] , 1); ans2[i]=query(vlez[i]-1); } LL ans=0; for (int i=0;i<n;i++) ans+=(ans1[i]*ans2[i]); cout><<ans; return 0; }
Forum Index
»
Задачи од национални натпревари
Go to:
Select a forum
Добродојдовте!
Општа дискусија
Задачи од национални натпревари
Задачи од меѓународни натпревари
Други задачи
Регионални натпревари
Државни натпревари
Македонски Олимпијади
Други натпревари
Pascal
C/C++
Јава
Други јазици
Powered by
JForum 2.1.8
©
JForum Team