1090
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> using namespace std; typedef vector<int> vi; typedef vector<string> vs; typedef vector<vi> vvi; typedef pair<int,int> ii; #define sz(a) int((a).size()) #define pb push_back #define all(c) (c).begin(),(c).end() //#define tr(c,i) for(typeof((c).begin() i = (c).begin(); i != (c).end(); i++) #define present(c,x) ((c).find(x) != (c).end()) #define cpresent(c,x) (find(all(c),x) != (c).end()) #define FOR(_i,_n) for(int _i = 0; _i < _n; _i++) #define INPUT_FILE "xo.in" #define OUTPUT_FILE "xo.out" #define N 10000+10 #define prev(x) ((x)&(x-1)) #define next(x) ((x<<1)-(x&(x-1))) int A[N];// = {0}; int S[N];// = {0}; void init() { for(int i = 0; i < N; i++) S[i] = 0; } // A[pos] + value // value - любого знака // pos >= 1 void modify(int pos, int value) { int x = pos; while(x < N) { S[x] += value; x = next(x); } } // A[l] + A[l+1] + ... + A[r] // l,r >= 1 // l <= r long long findsum(int l, int r) { long long sum = 0; int x = r; while(x > 0) { sum += S[x]; x = prev(x); } x = l - 1; while(x > 0) { sum -= S[x]; x = prev(x); } return sum; } int main(void) { #ifdef ALEX freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #else // freopen(INPUT_FILE, "r", stdin); // freopen(OUTPUT_FILE, "w", stdout); #endif int n,k; int row = -1; int rr = -1; cin >> n >> k; FOR(i,k) { int r = 0; init(); FOR(j,n) { int t; scanf("%d", &t); r += findsum(t, n); modify(t, 1); } if(r > rr) { rr = r; row = i+1; } #ifdef ALEX cout << "r = " << r << endl; #endif } cout << row; return 0; }
page revision: 0, last edited: 22 Apr 2007 09:44